n gas stations sit in a circle, numbered 0 to n-1. At station i your car can pick up gas[i] units of fuel, and driving from station i to station i+1 (wrapping after the last back to station 0) costs cost[i] units. Your tank starts empty and has unlimited capacity, and it must never go negative at any point of the trip.
You want to start at some station, drive once around the entire circle, and return to the start. Report the smallest station index from which the full loop is possible, or -1 if no starting station works.
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers gas[0..n-1].
Line 3: n space-separated non-negative integers cost[0..n-1].
Output format
A single integer: the smallest valid starting index (0-indexed), or -1 if the loop cannot be completed from any station.
Constraints
- 1 <= n <= 100000
- 0 <= gas[i] <= 1000000000
- 0 <= cost[i] <= 1000000000