A courier drives a fixed clockwise loop past n fuel depots numbered 0 to n-1. At depot i the courier picks up gas[i] litres, and driving from depot i to the next depot (i+1) mod n burns cost[i] litres. The tank starts empty at the chosen depot and must never drop below zero at any point of the loop.
Among all depots from which the entire loop can be completed, output the smallest index. If no depot works, output -1.
Input format
Line 1: an integer n.
Line 2: n space-separated integers, the gas values.
Line 3: n space-separated integers, the cost values.
Output format
A single integer: the smallest valid starting depot index (0-based), or -1 if none exists.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ gas[i] ≤ 1000000000
- 0 ≤ cost[i] ≤ 1000000000