Cho dãy số nguyên \(a_1, a_2, ..., a_n\) \((1 \le n \le 100000)\), mỗi số không vượt qúa \(10000\). Dãy số này được viết trên một vòng tròn. Nghĩa là, khi cắt vòng tròn tại vị trí \(j\), ta thu được:

\(a_j, a_{j+1},..., a_n, a_1, a_2, ..., a_{j–1}\)

Vị trí \(j\) được gọi là vị trí tốt, nếu các điều kiện sau đây được thỏa mãn:

• \(a_j \gt 0\)
• \(a_j + a_{j+1} \gt 0\)
• ....
• \(aj + a_j+1 + ... + a_n > 0\)
• \(a_j + a_j+1 + ... + a_n + a_1 > 0\)
• ...
• \(a_j + a_j+1 + ... + a_n + a_1 + a_2 + ... + a{j─2} > 0\)
• \(a_j + a_j+1 + ... + a_n + a_1 + a_2 + ... + a{j─2} + a{j─1} > 0\)

Input

• Dòng đầu tiên chứa số nguyên n.
• Dòng thứ 2 chứa dãy số a1, a2,...,an.

Output

• In ra 1 số nguyên duy nhất là số vị trí tốt.

Example

Sample input

5
0 1 -2 10 3

Sample output

2