题目描述

Uim 在公司里面当秘书，现在有 $n$ 条消息要告知老板。每条消息有一个好坏度，这会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条消息的好坏度。 最开始老板的心情是 $0$，一旦老板心情到了 $0$ 以下就会勃然大怒，炒了 Uim 的鱿鱼。

Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望知道如何才能不让老板发怒。

Uim 必须按照事件的发生顺序逐条将消息告知给老板。不过 Uim 可以使用一种叫"倒叙"的手法，例如有 $n$ 条消息， Uim 可以任取一个整数 $k\;(1 \le k \le n)$，先从 $k$ 事件通报到 $n$ 事件，再从 $1$ 事件通报到 $k-1$ 事件。特别的，当 $k = 1$ 时按照原顺序通报。

他希望知道，有多少个这样的 $k$ 可以让老板不发怒。

输入格式

第一行一个整数 $n\;(1 \le n \le 10^6)$，表示有 $n$ 个消息。

第二行 $n$ 个整数，按时间顺序给出第 $i$ 条消息的好坏度 $A_i\;(-10^3 \le A_i \le 10^3)$。

输出格式

一行一个整数，表示可行的方案个数。

4
-3 5 1 2

2

数据规模与约定

【样例解释】

通报事件的可行顺序（用编号表示）为 $2 \rightarrow 3 \rightarrow 4 \rightarrow 1$ 或 $3 \rightarrow 4 \rightarrow 1 \rightarrow 2$（分别对应 $k = 2$ 和 $k = 3$）

通报事件的可行顺序（用好坏度表示）为 $5 \rightarrow 1 \rightarrow 2 \rightarrow (-3)$ 或 $1 \rightarrow 2 \rightarrow (-3) \rightarrow 5$

【数据范围】

对于 $25\%$ 的数据，$n \le 10^3$；

对于 $75\%$ 的数据，$n \le 10^4$；

对于 $100\%$ 的数据，$1 \le n \le 10^6$。