GreedyArray
There are n gas stations on a circular route. Station i gives you gas[i] units of fuel, and driving from station i to the next one costs cost[i] units. You start with an empty tank at one station. Find the index of the station where you can start and complete one full loop clockwise, or report -1 if it is impossible. If a solution exists it is unique.
Input
Line 1: n. Line 2: the n values of gas. Line 3: the n values of cost.
Output
Print the starting station index, or -1.
Constraints
1 <= n <= 10^5 0 <= gas[i], cost[i] <= 10^4
Example 1
Input
5 1 2 3 4 5 3 4 5 1 2
Output
3
Starting at index 3 you can finish the loop.
Example 2
Input
3 2 3 4 3 4 3
Output
-1
The total cost exceeds the total gas, so it is impossible.