Cho dãy số nguyên a1, a2, ..., an (~1 \leq n \leq 100000~), mỗi số không vượt quá 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}~ ~>~ 0
• ~a_{j}~ + ~a_{j+1}~ ~>~ 0
• ....
• ~a_{j}~ + ~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

Yêu cầu: hãy đếm số vị trí tốt.

Input

• Dòng đầu tiên chứa số nguyên n.
• Dòng thứ 2 chứa dãy số ~a_1~, ~a_2~,...,~a_{n}~.

Output

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

Sample Input

5
0 1 -2 10 3

Sample Output

2