我们的小男孩 Askhat 注意到了一个有趣的现象——尝试用越来越大的“跳跃”和来覆盖一个数组可能并不像看起来那么简单。当然，现在你需要找到一种方法来实现它。

给定一个长度为 $N$ 的正整数序列。

将给定的序列划分为尽可能多的段，使得：

1. 序列中的每个元素恰好属于一个段。
2. 除了第一段外，每一段的数字之和都不小于前一段的数字之和。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 5 \cdot 10^5$)。

第二行包含 $N$ 个正整数 $a_i$ ($1 \le a_i \le 10^9$)，以空格分隔。

输出格式

输出一个整数——该序列可以被划分成的最大段数。

子任务

本题包含五个子任务，具有额外的约束条件：

1. $1 \le N \le 20$，$a_i \le 10^6$。分值为 13 分。
2. $1 \le N \le 500$。分值为 14 分。
3. $1 \le N \le 3000$。分值为 10 分。
4. $1 \le N \le 10^5$。分值为 36 分。
5. 原始约束条件。分值为 27 分。

样例

样例输入 1

4
2 3 1 7

样例输出 1

3

样例输入 2

5
6 2 3 9 13

样例输出 2

3

样例输入 3

3
3 1 2

样例输出 3

2