小さな男の子 Askhat は、興味深い現象に気づきました。配列を「ジャンプ」しながら、より大きな合計値で覆っていくことは、見た目ほど単純ではないかもしれません。もちろん、あなたはその方法を見つけ出す必要があります。

長さ $N$ の正の整数の数列が与えられます。この数列を、以下の条件を満たすように可能な限り多くのセグメントに分割してください。

1. 数列のすべての要素は、ちょうど1つのセグメントに属する。
2. 最初のセグメントを除くすべてのセグメントの合計値は、その直前のセグメントの合計値以上である。

入力

入力の最初の行には整数 $N$ ($1 \le N \le 5 \cdot 10^5$) が含まれます。 次の行には、$N$ 個の正の整数 $a_i$ ($1 \le a_i \le 10^9$) がスペース区切りで含まれます。

出力

与えられた数列を分割できるセグメントの最大数を、単一の整数として出力してください。

小課題

この課題には5つの小課題があり、追加の制約が課されます。

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