Non-negative Partial Sums |

You are given a sequence of *n* numbers
*a*_{0},..., *a*_{n-1}.
A cyclic shift by *k* positions (
0*k**n* - 1) results in the following sequence:
*a*_{k}, *a*_{k+1},..., *a*_{n-1}, *a*_{0}, *a*_{1},..., *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*i**n*?

Each test case consists of two lines.
The first contains the number *n* (
1*n*10^{6}), the number of integers in the sequence.
The second contains *n* integers
*a*_{0},..., *a*_{n-1} (
-1000*a*_{i}1000) representing the sequence of numbers.
The input will finish with a line containing 0.

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