题目描述

孙悟空有n条消息要告知唐僧。每条消息有一个好坏度，这会影响唐僧的心情。告知完一条消息后，唐僧的心情等于之前唐僧的心情加上这条消息的好坏度。最开始唐僧的心情是0，一旦心情到了0以下就会念紧箍咒。
孙悟空为了不被念紧箍咒，在知道了这些消息（已经按时间的发生顺序进行了排列）的好坏度，希望研究如何不让唐僧发怒。
孙悟空必须按照时间的发生顺序逐条将消息告知给唐僧。不过他可以使用一种叫“倒叙”的手法，例如有n条消息，孙悟空可以从k,k+1,k+2...n,1,2...k-1这种顺序通报。
他希望知道，有多少个k，从k开始通报到n然后从1通报到k-1可以让唐僧不发怒。

输入格式：

第一行一个整数n(1 <= n <= 10^6)，表示有n个消息。
第二行n个整数，按时间顺序给出第i条消息的好坏度Ai(-1000 <= Ai <= 1000)

输出格式：

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

输入样例#1：

4
-3 5 1 2 

输出样例#1：

2

数据范围

对于 25% 的数据，n≤10^3 ；
对于 75% 的数据，n≤10^4 ；
对于 100% 的数据，1≤n≤10^6 。