Cyclotron Accelerator Problem

In this problem, you are given a simplified model of a cyclotron accelerator. The accelerator is modeled as a circular track with n accelerating cavities numbered from 1 to n. A proton beam is injected into one of these cavities with an initial kinetic energy of zero. When the proton reaches a cavity, it immediately receives additional kinetic energy equal to that cavity's provided energy. However, when the proton travels from cavity i to cavity i+1 (with cavity n connecting back to cavity 1), it loses a fixed amount of kinetic energy. During the travel between two cavities, the kinetic energy must remain strictly greater than zero, although it is allowed to be zero just upon arrival (since the cavity will then instantly provide its energy).

Formally, you are given two arrays:

• e[1..n]: where e_i is the kinetic energy provided by the i-th cavity.
• d[1..n]: where d_i is the energy lost when traveling from the i-th cavity to the (i+1)-th cavity (with the n-th connected to the 1st).

If a proton beam is injected at cavity s, the process is as follows:

1. At the start, the kinetic energy is 0.
2. At cavity s, the energy becomes e_s.
3. Then, for each cavity in order for a complete cycle, subtract d_i when moving to the next cavity. The resulting energy must be > 0 before arriving at the next cavity. Upon arrival, the proton immediately receives additional energy from that cavity.

Your task is to determine if there exists a starting cavity s such that the proton can complete one full circuit without the energy dropping to zero or below during any transit. If such a starting point exists, output its 1-indexed position; otherwise, output -1.

The formulas used in the simulation are given by: [ E_{next} = (E_{current} + e_i) - d_i, \quad \text{with } E_{next} > 0. ]

Note: The energy may be zero upon arrival at a cavity, because the cavity then immediately adds its energy.

Good luck!

inputFormat

The input consists of three lines:

• The first line contains a single integer n (the number of cavities).
• The second line contains n space-separated integers representing the energy gains e1, e2, …, en provided by each cavity.
• The third line contains n space-separated integers representing the energy losses d1, d2, …, dn when moving from each cavity to the next (with the n-th cavity connecting to the first).

outputFormat

Output a single integer. If there exists a valid starting cavity (1-indexed) from which the proton can make a full cycle without the energy falling to zero or below during transit, output its index. Otherwise, output -1.

sample

4
4 6 7 4
6 5 3 5

2