问题描述

一款游戏中有 n 个关卡，每个关卡通关后会改变玩家的积分（可正可负）。玩家需要选择一个起始关卡 $k$ $(1 \leq k \leq n)$，按照 “从第 $k$ 关依次通到第 n 关，再从第 $1$ 关依次通到第 $(k-1)$ 关” 的顺序完成所有关卡（当 $(k=1)$ 时，直接按原顺序 $1$ 到 $n$ 通关）。玩家初始积分为 $0$，若通关过程中积分任何时刻低于 $0$，则挑战失败。请问有多少个起始关卡 $k$ 能让玩家成功完成所有关卡？

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 10^6)$，表示关卡的数量。

第二行 $n$ 个整数，按顺序给出第 $i$ 关通关后的积分变化值（可正可负）。

输出格式

一行一个整数，表示能让玩家成功完成所有关卡的起始关卡 $k$ 的数量。

输入样例

4
-3 5 1 2

输出样例

2

评测数据规模

对于所有评测数据， $1 \leq n \leq 10^6$,且每个关卡的积分变化值在 $[-10^3, 10^3]$ 范围内。