A delivery van drives a circular route through n stops. At stop i it can take fuel[i] litres; reaching the next stop (i + 1, and from the last back to the first) uses cost[i] litres. The van starts with an empty tank.
Print the smallest stop index (0-based) from which it can complete the full circle, or -1 if no start works.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ fuel[i], cost[i] ≤ 10000
Input and output
- Input
- Line 1: n. Line 2: fuel[0..n−1]. Line 3: cost[0..n−1].
- Output
- One integer.
Examples
Input 1
4
4 6 7 4
6 5 3 5Output
1Starting at stop 1: tank goes 6−5=1, then 1+7−3=5, then 5+4−5=4, then 4+4−6=2. Every leg is covered.
Input 2
3
1 2 3
2 3 4Output
-1Total fuel (6) is less than total distance (9), so no start works.
Show hints
- If total fuel < total cost, no start can work.
- If the tank goes negative on the way from start s to stop i, no stop between s and i can be a valid start either.
Show the explanation
Two facts give a one-pass greedy. First, a route exists only if total fuel ≥ total cost. Second, if you start at s and run dry before reaching i + 1, then starting anywhere between s and i fails too (you would arrive at each of them with at least as much fuel as when starting fresh). So whenever the running tank drops below zero, restart at i + 1 with an empty tank. The last restart point is the answer, and it is also the smallest valid start.
Original UniCircle question. Last reviewed 22 Oct 2026.