Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le n \le 10^5\)), 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}, \dots, a_n, a_1, a_2, \dots, 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\)
• \(\dots\)
• \(a_j + a_{j+1} + \dots + a_n > 0\)
• \(a_j + a_{j+1} + \dots + a_n + a_1 > 0\)
• \(\dots\)
• \(a_j + a_{j+1} + \dots + a_n + a_1 + a_2 + \dots + a_{j-2} > 0\)
• \(a_j + a_{j+1} + \dots + a_n + a_1 + a_2 + \dots + 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, \dots, a_n\).

Output

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

Constraints

• \(1 \le n \le 10^5\)
• \(|a_i| \le 10^4\)

Example

5
0 1 -2 10 3

2