Problem H
Non-negative Partial Sums

You are given a sequence of $n$ numbers $a_0, \ldots , a_{n-1}$. A cyclic shift by $k$ positions ($0 \le k \le n-1$) results in the following sequence: $a_ k, a_{k+1}, \ldots , a_{n-1}, a_0, a_1, \ldots , a_{k-1}$. How many of the $n$ cyclic shifts satisfy the condition that the sum of the first $i$ numbers is greater than or equal to zero for all $i$ with $1 \le i \le n$?

Input

The input contains at most 110 testcases. Each test case consists of two lines. The first contains the number $n$ ($1 \le n \le 10^6$), the number of integers in the sequence. The second contains $n$ integers $a_0, \ldots , a_{n-1}$ ($-1000 \le a_ i \le 1000$) representing the sequence of numbers. The input will finish with a line containing $0$.

Output

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.

3
2 2 1
3
-1 1 1
1
-1
0

3
2
0