题目描述

你有 $n$ 条工作消息需要向老板汇报，每条消息有一个"好坏度" $A_i$。老板的初始心情值为 $0$，每汇报一条消息，心情值就加上 $A_i$。如果在汇报过程中老板的心情值变为负数（$\lt 0$），老板就会发怒。

你可以选择一个整数 $k$（$1 \le k \le n$），按照 $A_k, A_{k+1}, \ldots, A_n, A_1, A_2, \ldots, A_{k-1}$ 的顺序汇报。求有多少种不同的 $k$ 的选择，使得老板在整个汇报过程中心情值始终非负。

输入格式

第一行一个正整数 $n$，表示消息的数量。

第二行 $n$ 个整数 $A_1, A_2, \ldots, A_n$，表示每条消息的好坏度。

输出格式

输出一行一个整数，表示满足条件的 $k$ 的个数。

样例

4
-3 5 1 2

2

提示

• $1 \le n \le 10^6$
• $-10^3 \le A_i \le 10^3$