Gas Station Circuit

You are given a circular route with n checkpoints. At each checkpoint i, you have fuel[i] units of fuel available, and you need cost[i] units of fuel to travel from checkpoint i to the next checkpoint. Your task is to determine the starting checkpoint index from which the vehicle can complete the entire circuit successfully. If it is impossible to complete the circuit, return -1.

Mathematically, the circuit can be completed if and only if \[ \sum_{i=0}^{n-1} fuel[i] \geq \sum_{i=0}^{n-1} cost[i] \] If the condition fails then the journey is impossible, otherwise, use a greedy strategy to determine the smallest starting index that allows for a complete circuit.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains an integer n, the number of checkpoints.
• The second line contains n space-separated integers representing the fuel available at each checkpoint.
• The third line contains n space-separated integers representing the fuel cost to travel from each checkpoint to the next.

outputFormat

Output a single integer to stdout representing the starting checkpoint index from which the vehicle can complete the circuit. If it is not possible, output -1.

5
1 2 3 4 5
3 4 5 1 2

3