PARSUMS  Nonnegative 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?
Input
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.
Output
For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.
Sample Input
3 2 2 1 3 1 1 1 1 1 0
Sample Output
3 2 0
Problemsetter: Adrian Kuegel
hide comments
Sahil Sharma:
20150113 07:13:57
Hi,


AlcatraZ:
20140422 23:11:32
Nice and Tricky.. ;) 

Ankit Jain:
20140104 13:21:55
logical question 

BOND:
20111222 17:26:35
@accept


accept:
20111222 10:54:07
what's mean of first i number..


BOND:
20111221 15:54:38
edit got it Last edit: 20120526 12:50:59 

Adrian Kuegel:
20111215 14:32:28
Please tell which part is unclear to you.


Vratika Ghatiya:
20111215 14:24:20
Please elaborate i !!


sri:
20111203 09:34:10
what is the value of i???


M@@Y@:
20111203 06:03:16
@Raja .... its " How many of the n cyclic shifts " ...i guess i m making things clear. 
Added by:  David GarcĂa Soriano 
Date:  20111126 
Time limit:  8.989s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Southwestern Europe Regional, SWERC 2011 