Non-negative Partial Sums

You are given a sequence of $n$ numbers $a_0, a_1, \dots, a_{n-1}$. A cyclic shift by $k$ positions ($0 \le k \le n - 1$) produces the sequence $$a_k, a_{k+1}, \dots, a_{n-1}, a_0, a_1, \dots, a_{k-1}.$$ Count how many of the $n$ cyclic shifts satisfy the following condition: the sum of the first $i$ numbers of the shifted sequence is greater than or equal to zero for every $i$ with $1 \le i \le n$.

The input contains several test cases.

Each test case consists of two lines. The first line contains the integer $n$ ($1 \le n \le 10^6$), the number of integers in the sequence. The second line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$ ($-1000 \le a_i \le 1000$) describing the sequence.

The input ends with a line containing a single $0$.

For each test case, print one line containing the number of cyclic shifts of the given sequence that satisfy the condition above.