City cycle

You are given ~N~ cities, numbered from ~1~ to ~N~ (inclusive), arranged along a circular route (the next city after city ~k~ in the circular route is city ~k + 1~, when ~k < N~, and city ~1~ when ~k = N~). A government employee is going to visit all the cities in the order mentioned and settle the tax arrears of the citizens to the state (tax payment) and of the state to the citizens (tax refund) in each city. For each city ~k~ (where ~1 \le k \le N~), an integer ~b_k~ is given, which equals the sum of the tax arrears of the residents of city ~k~ (this number can be positive, negative, or ~0~). So if ~b_k~ is positive, the employee leaves city ~k~ with ~b_k~ euros more than he had when he arrived, if ~b_k~ is negative, the employee leaves city ~k~ with |~b_k~| euros less, and if ~b_k~ is ~0~, the employee leaves city ~k~ with the same amount of money available. The employee cannot continue his tour if it appears that he has a negative amount after visiting a city, as this indicates an inability to fulfill some tax refund obligations in the city.

Problem

Write a program to find the first city (i.e., the one with the smallest number) from which the government employee can start his tour with zero euros and still be able to complete it.

Input File

The first line of the input will contain the number of cities ~N~. The second line of the input will contain the ~N~ integers ~b_1~, ~b_2~, ~...~, ~b_N~, separated by spaces.

Output File

The output should consist of a single line containing exactly one natural number: the number of the first city from which the government employee can start his tour with zero euros and still be able to complete it. If there is no such city, the number in the output should be ~0~.

Examples of Input - Output Files:

1st

STDIN (citycirc.in)

6
-50 20 15 30 0 -5

STDOUT (citycirc.out)

2

2nd

STDIN (citycirc.in)

8
35 10 -55 -40 30 -70 60 30

STDOUT (citycirc.out)

7

3d

STDIN (citycirc.in)

6
-50 20 -15 30 18 -5

STDOUT (citycirc.out)

0

Constraints

• ~2 \le N \le 2.000.000~.