题目背景

al7在游戏中抽两百发歪了六个金，没有得到自己想要的角色，现在他相对这个世界失望透顶。毁灭吧，累了。

题目描述

al7随机选择了一名十连双金的幸运儿M2cfrst进行死亡游戏。游戏在一个长度为n的轮盘上进行，顺时针编号依次为1,2,.....,n,每个位置上有一个整数（可以为负），记为$a_i$。

al7会选择1,2,....,n中的一个数k，并且让M2cfrst从k开始（先踩在k这个格子上）顺时针走n-1步，依次踩上k,k+1,.....,n,1,.....,k-1这些格子。M2cfrst每踩上一个格子就会将自己的生命值加上这个格子上的数，如果在某次生命值改变后为负数，则M2cfrst就要晚安了。M2cfrst的初始生命值为0。M2cfrst想知道有多少个不同的k使得它可以最终活下来。

输入格式

第一行一个整数n。 接下来一行n个整数，第i个数字代表$a_i$。

输出格式

唯一一行一个整数，表示答案。

数据范围

对于所有测试点：$n\leq3*10^5，|a_i|\leq10^9$；

任务点1，测试点编号1-4，满足$n\leq10^3$

任务点2，测试点编号5-12，满足$|a_i|\leq1$

任务点3，测试点编号13-20，无特殊限制

样例

4
-3 4 1 2

2

样例解释1

只有4和1的位置是合理位置，-3位置开局直接负数，2位置在走到-3，变成负数-1。

时间空间限制

1000ms，262144K