D. Keine's Prefix Sum
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Keine is a teacher in Touhou Eiyashou. One day she gives you a problem in her class:

Give you an array $$$a_i$$$, we define $$$s_i$$$ as the prefix sum of $$$a_i$$$ (In other words, $$$s_i=\sum^i_{j=1}a_j$$$). Assume that an array $$$a_i$$$ is $$$\textbf{good}$$$ if and only if each $$$s_i$$$ satisfies $$$s_i \ge 0$$$.

Now Keine will perform a cyclic placement operation for $$$n$$$ times: Place $$$a_1$$$ behind $$$a_n$$$, which means that $$$[a_1,a_2...a_{n-1},a_n]$$$ will change to $$$[a_2,a_3...a_n,a_1]$$$. Then Keine will ask you whether the array $$$a_i$$$ is $$$\textbf{good}$$$.

Please output the number of $$$\textbf{good}$$$ arrays.

Input

The first line consists of a positive integer $$$n\ (1\le n\le 10^5)$$$.

The second line consists of n positive integers $$$a_i\ (-10^3\le a_i\le 10^3)$$$.

Output

The number of $$$\textbf{good}$$$ arrays.

Example
Input
5
2 3 -4 1 -1
Output
2
Note

There are $$$5$$$ arrays that you need to check:

  • $$$[2,3,-4,1,-1]$$$

  • $$$[3,-4,1,-1,2]$$$

  • $$$[-4,1,-1,2,3]$$$

  • $$$[1,-1,2,3,-4]$$$

  • $$$[-1,2,3,-4,1]$$$

The first and the fourth arrays are $$$\textbf{good}$$$.