我們的小男孩 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