

Nonnegative Partial SumsTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4747 Accepted Submission(s): 1553 Problem Description You are given a sequence of n numbers a_{0},..., a_{n1}. A cyclic shift by k positions (0<=k<=n1) results in the following sequence: a_{k} a_{k+1},..., a_{n1}, a_{0}, a_{1},..., a_{k1}. 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_{n1} (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
Sample Output
Source  
