PARSUMS - Nonnegative Partial Sums

You are given a sequence of n numbers a0, …, an−1. A cyclic shift by k positions (0 ≤ kn−1) results in the following sequence: ak, ak+1, …, an−1, a0, a1, …, ak−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 ≤ in?



Input

Each test case consists of two lines. The first contains the number n (1 ≤ n ≤ 106), the number of integers in the sequence. The second contains n integers a0, …, an−1 (−1000 ≤ ai ≤ 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

Added by:David GarcĂ­a Soriano
Date:2011-11-26
Time limit:8.989s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Southwestern Europe Regional, SWERC 2011

hide comments
2011-12-03 06:03:16 M@@Y@
@Raja .... its " How many of the n cyclic shifts " ...i guess i m making things clear.
2011-11-30 03:37:14 R@ja.... -[^_^]-
how come the output for 1st case is 3...will 0 shift not do..???? pl help..

Last edit: 2011-11-30 03:38:09
2011-11-27 18:48:40 Kazi Rakibul Hossain
nice problem :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.