Non-negative Partial Sums#3070
You are given a sequence of numbers a_0, \ldots, a_{n-1}. A cyclic shift by positions (0 \leq k \leq n-1) produces the following sequence: a_k, a_{k+1}, \ldots, a_{n-1}, a_0, a_1, \ldots, a_{k-1}. How many of the cyclic shifts satisfy the condition that the sum of the first numbers is greater than or equal to zero for all with 1 \leq i \leq n?
Each test case consists of two lines. The first line contains the number (1 \leq n \leq 10^6), the number of integers in the sequence. The second line contains integers a_0, \ldots, a_{n-1} (-1000 \leq a_i \leq 1000), representing the sequence. The input ends with a line containing .
For each test case, print one line with the number of cyclic shifts of the given sequence which satisfy the condition stated above.
Example 1