190. The Circular Tour
Petrol pumps are arranged in a circle. At pump i you can collect
petrol[i] litres, and it costs distance[i] litres to drive from pump i to the next
one.
Starting with an empty tank, find the first pump you could start from and complete the whole circle without the tank ever going negative.
Print the pump number, counting from 1, or -1 if no starting point works.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ petrol ≤ 1000000` - `0 ≤ distance ≤ 1000000`
Input
The first line contains an integer n, the number of pumps.
Each of the next n lines contains two integers, the petrol available at that pump, and the distance to the next pump.
Output
Print one integer, the 1-based number of the first pump from which the whole circle can be completed, or -1 if there is none.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.