Description

Uim 在公司里面当秘书，现在有 n 条消息要告知老板。每条消息有一个好坏度，这
会影响老板的心情。告知完一条消息后，老板的心情等于老板之前的心情加上这条
消息的好坏度。最开始老板的心情是 0，一旦老板心情到了 0 以下就会勃然大怒，
炒了 Uim 的鱿鱼。
Uim 为了不被炒，提前知道了这些消息（已经按时间的发生顺序进行了排列）的好
坏度，希望知道如何才能不让老板发怒。
Uim 必须按照事件的发生顺序逐条将消息告知给老板。不过 Uim 可以使用一种叫
“倒叙” 的手法，例如有 n 条消息，Uim 可以按k,k+1,k+2...,n,1,2...,k-1（事件编号）
这种顺序通报。
他希望知道，有多少个 k ，可以使从 k 号事件开始通报到 n 号事件然后再从 1 号事
件通报到 k-1 号事件可以让老板不发怒。

Input Format

第一行一个整数 n(1<=n<=1e6)，表示有n个消息。
第二行 个整数，按时间顺序给出第 条消息的好坏度 Ai(-1e3<=Ai<=1e3)。
【数据范围】
对于25% 的数据，n<=1e3 .
对于75% 的数据，n<=1e4 .
对于100% 的数据，1<=n<=1e6 .

Output Format

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


【样例解释】
通报事件的可行顺序（用编号表示）为 2->3->4->1或3->4->1->2
（分别对应k=2 和 k=3）
通报事件的可行顺序（用好坏度表示）为 5->1->2->(-3)或1->2->(-3)->5

4
-3 5 1 2

2

Source

单调队列