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 fi rst i numbers is greater than or equal to zero for all i with 1 ≤ i ≤ n?
Input
Each test case consists of two lines. The fi rst 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.
Output
For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.