On a circular patrol route, there are $n$ supply points, numbered $1,2,\dots,n$ in clockwise order. The patrol inspector may choose any supply point as the starting point, then travel clockwise through all supply points and eventually return to the starting point.

The $i$-th supply point changes the inspector's current charge by $a_i$:

• If $a_i>0$, the charge increases by $a_i$ when passing this point;
• If $a_i<0$, the charge decreases by $|a_i|$ when passing this point;
• If $a_i=0$, the charge remains unchanged.

During the whole patrol, the charge must never drop below $0$. The inspector's initial charge is $0$. If, starting from some point, while moving along the loop and passing all supply points in order, the charge is no less than $0$ at every moment, then this starting point is called a valid starting point.

You need to count how many valid starting points there are.

Input

The first line contains an integer $n$ ($1\le n\le 2\times 10^5$), the number of supply points.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($-10^9\le a_i\le 10^9$), where $a_i$ is the change in charge when passing the $i$-th supply point.

Output

Output one integer: the number of valid starting points.

Examples

Input 1

5
1 -2 3 -1 2

Output 1

2

Input 2

4
0 0 0 0

Output 2

4

Note

Sample 1:

When starting from point $1$, the charge changes encountered are $1,-2,3,-1,2$, and the prefix sums are $1,-1,2,1,3$. Since the charge once dropped to $-1$, point $1$ is not a valid starting point.

When starting from point $2$, the charge drops to $-2$ at the first step, so point $2$ is not a valid starting point.

When starting from point $3$, the charge changes encountered are $3,-1,2,1,-2$, and the prefix sums are $3,2,4,5,3$. During the whole process, the charge is never less than $0$, so point $3$ is a valid starting point.

When starting from point $4$, the charge drops to $-1$ at the first step, so point $4$ is not a valid starting point.

When starting from point $5$, the charge changes encountered are $2,1,-2,1,-2$, and the prefix sums are $2,3,1,2,0$. During the whole process, the charge is never less than $0$, so point $5$ is also a valid starting point.

In summary, there are $2$ valid starting points in total: point $3$ and point $5$.

Sample 2:

No matter which point is chosen as the starting point, the charge remains $0$ throughout the whole process, so all four points are valid starting points.