在一条环形巡检路线上，一共有 $n$ 个补给点，按顺时针依次编号为 $1,2,\dots,n$。巡检员可以选择任意一个补给点作为起点，然后沿顺时针方向依次经过所有补给点，最终回到起点。

第 $i$ 个补给点会使巡检员当前携带的电量发生变化，变化量为 $a_i$：

• 若 $a_i>0$，表示经过该点时电量增加 $a_i$；
• 若 $a_i<0$，表示经过该点时电量减少 $|a_i|$；
• 若 $a_i=0$，表示电量不变。

巡检员要求，在整个巡检过程中，电量始终不能降到 $0$ 以下。 巡检员的初始电量为0，如果从某个起点出发后，在沿环行进并依次经过所有补给点的过程中，任意时刻的电量都不小于 $0$，则称这个起点是合法起点。

你需要求出一共有多少个合法起点。

Input

第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$），表示补给点的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9\le a_i\le 10^9$），其中 $a_i$ 表示经过第 $i$ 个补给点时电量的变化量。

Output

输出一个整数，表示合法起点的数量。

Examples

Input 1

5
1 -2 3 -1 2

Output 1

2

Input 2

4
0 0 0 0

Output 2

4

Note

样例 1：

从第 $1$ 个点出发时，依次经过的电量变化为 $1,-2,3,-1,2$, 前缀和依次为 $1,-1,2,1,3$。由于电量曾降至 $-1$，因此第 $1$ 个点不是合法起点。

从第 $2$ 个点出发时，第一步电量就降至 $-2$，因此第 $2$ 个点不是合法起点。

从第 $3$ 个点出发时，依次经过的电量变化为 $3,-1,2,1,-2$，前缀和依次为 $3,2,4,5,3$。整个过程中电量始终不小于 $0$，因此第 $3$ 个点是合法起点。

从第 $4$ 个点出发时，第一步电量就降至 $-1$，因此第 $4$ 个点不是合法起点。

从第 $5$ 个点出发时，依次经过的电量变化为 $2,1,-2,1,-2$，前缀和依次为 $2,3,1,2,0$ 整个过程中电量始终不小于 $0$，因此第 $5$ 个点也是合法起点。

综上，合法起点共有 $2$ 个，分别为第 $3$ 个点和第 $5$ 个点。

样例 2：

任意位置作为起点，整个过程中电量都始终保持为 $0$，因此四个点都是合法起点。