#P2629. 好消息,坏消息

    ID: 1636 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>线性结构单调队列前缀和队列

好消息,坏消息

题目描述

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

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

Uim 必须按照事件的发生顺序逐条将消息告知给老板。不过 Uim 可以使用一种叫 “倒叙” 的手法,例如有 nn 条消息,Uim 可以按 k,k+1,k+2,,n,1,2,,k1k,k+1,k+2,\ldots,n,1,2,\ldots,k-1(事件编号)这种顺序通报。

他希望知道,有多少个 kk,可以使从 kk 号事件开始通报到 nn 号事件然后再从 11 号事件通报到 k1k-1 号事件可以让老板不发怒。

输入格式

第一行一个整数 nn1n1061 \le n \le10^6),表示有 nn 个消息。

第二行 nn 个整数,按时间顺序给出第 ii 条消息的好坏度 AiA_i103Ai103-10^3\le A_i \le 10^3)。

输出格式

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

4
-3 5 1 2

2

提示

【样例解释】

通报事件的可行顺序(用编号表示)为 23412\rightarrow3\rightarrow4\rightarrow134123\rightarrow4\rightarrow1\rightarrow2(分别对应 k=2k=2k=3k=3

通报事件的可行顺序(用好坏度表示)为 512(3)5\rightarrow1\rightarrow2\rightarrow(-3)12(3)51\rightarrow2\rightarrow(-3)\rightarrow5

【数据范围】

对于 25%25\% 的数据,n103n\le10^3
对于 75%75\% 的数据,n104n\le10^4
对于 100%100\% 的数据,1n1061 \le n\le 10^6