Around the Circuit

Difficulty: 1600 3000 ms 128 MB

greedy

N stations sit on a circular route. Station i provides gas_i fuel; driving to the next station costs cost_i. Starting with an empty tank at some station, print the 1-based index of the unique valid starting station to complete a full lap, or −1 if none exists.

Input: the first line has N; the second line has gas_1..N; the third line has cost_1..N.

Output: the starting index, or −1.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ gas_i, cost_i ≤ 10⁴

Sample Tests

5
1 2 3 4 5
3 4 5 1 2

4

3
2 3 4
3 4 3

-1

Read the Editorial