eolymp
bolt
Try our new interface for solving problems
Problems

Non-negative Partial Sums

Non-negative Partial Sums

Time limit 1 second
Memory limit 64 MiB

You are given a sequence of n numbers a_0, ..., a_{n-1}. A cyclic shift by k positions (0kn-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 1in?

Input data

Each test case consists of two lines. The fi rst contains the number n (1n10^6), the number of integers in the sequence. The second contains n integers a_0, ..., a_{n-1} (-1000a_i ≤ 1000) representing the sequence of numbers. The input will finish with a line containing 0.

Output data

For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.

Examples

Input example #1
3
2 2 1
3
-1 1 1
1
-1
0
Output example #1
3
2
0