Nonnegative Partial Sums

You are given a sequence of n numbers a₀, …, 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₀, a₁, …, 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 Specification

Each test case consists of two lines. The first contains the number n (1 ≤ n ≤ 10⁶), the number of integers in the sequence. The second contains n integers a₀, …, a_n – 1 (–1000 ≤ a_i ≤ 1000) representing the sequence of numbers. The input will finish with a line containing “0”.

Output Specification

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

1. 3
2. 2 2 1
3. 3
4. -1 1 1
5. 1
6. -1
7. 0

download as text file

Output for Sample Input

1. 3
2. 2
3. 0

download as text file

Original Problem

Southwestern Europe Regional Contest, 2011