题目描述

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

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

Uim 必须按照事件的发生顺序逐条将消息告知老板。不过 Uim 可以使用一种叫“倒叙”的手法：例如有 $n$ 条消息，Uim 可以按顺序 $k, k+1, k+2, \dots, n, 1, 2, \dots, k-1$（事件编号）进行通报。

他希望知道，有多少个 $k$，使得从 $k$ 号事件开始通报到 $n$ 号事件，然后再从 $1$ 号事件通报到 $k-1$ 号事件，可以让老板不发怒（即任意时刻老板的心情始终非负）。

输入格式

第一行一个整数 $n$，表示有 $n$ 个消息。

第二行包含 $n$ 个整数，按时间顺序给出第 $i$ 条消息的好坏度 $A_i$。

输出格式

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

样例

4
-3 5 1 2

2

样例解释

• 当 $k=2$ 时，通报顺序为 $5, 1, 2, -3$，前缀和依次为 $5, 6, 8, 5$，均非负，满足条件。
• 当 $k=3$ 时，通报顺序为 $1, 2, -3, 5$，前缀和依次为 $1, 3, 0, 5$，均非负，满足条件。
• $k=1$ 时，通报顺序为 $-3, 5, 1, 2$，第一时刻前缀和即为 $-3 < 0$，不满足。
• $k=4$ 时，通报顺序为 $2, -3, 5, 1$，前缀和为 $2, -1 < 0$，不满足。 因此共有 $2$ 个 $k$ 满足要求。

数据范围与提示

• 对于 $25\%$ 的数据，$1 \le n \le 10^3$。
• 对于 $75\%$ 的数据，$1 \le n \le 10^4$。
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$-10^3 \le A_i \le 10^3$。

来源

单调队列