Notre petit Askhat a remarqué un phénomène intéressant : essayer de couvrir un tableau avec des « sauts » de sommes de plus en plus grandes n'est peut-être pas aussi simple qu'il y paraît. Bien sûr, vous devez maintenant trouver un moyen de le faire.

Vous disposez d'une séquence d'entiers positifs de longueur $N$.

Divisez la séquence donnée en un nombre maximal de segments de telle sorte que :

1. Chaque élément de la séquence appartienne à exactement un segment.
2. La somme des nombres de chaque segment, à l'exception du premier, ne soit pas inférieure à celle du segment précédent.

Entrée

La première ligne de l'entrée contient l'entier $N$ ($1 \le N \le 5 \cdot 10^5$). La ligne suivante contient $N$ entiers positifs $a_i$ ($1 \le a_i \le 10^9$), séparés par des espaces.

Sortie

Affichez un seul entier — le nombre maximal de segments en lesquels la séquence donnée peut être divisée.

Sous-tâches

Cette tâche contient cinq sous-tâches, avec des contraintes supplémentaires :

1. $1 \le N \le 20$, $a_i \le 10^6$. Rapportant 13 points.
2. $1 \le N \le 500$. Rapportant 14 points.
3. $1 \le N \le 3000$. Rapportant 10 points.
4. $1 \le N \le 10^5$. Rapportant 36 points.
5. Contraintes originales. Rapportant 27 points.

Exemples

Entrée 1

4
2 3 1 7

Sortie 1

3

Entrée 2

5
6 2 3 9 13

Sortie 2

3

Entrée 3

3
3 1 2

Sortie 3

2