Nasz mały chłopiec Askhat zauważył interesujące zjawisko — próba pokrycia tablicy „skokami” o coraz większych sumach może nie być tak prosta, jak się wydaje. Oczywiście teraz musisz znaleźć sposób, aby to zrobić.

Dana jest sekwencja dodatnich liczb całkowitych o długości $N$.

Podziel daną sekwencję na maksymalną liczbę segmentów tak, aby:

1. Każdy element sekwencji należał do dokładnie jednego segmentu.
2. Suma liczb w każdym segmencie, z wyjątkiem pierwszego, była nie mniejsza niż suma w poprzednim segmencie.

Wejście

W pierwszej linii wejścia znajduje się liczba całkowita $N$ ($1 \le N \le 5 \cdot 10^5$). W następnej linii znajduje się $N$ dodatnich liczb całkowitych $a_i$ ($1 \le a_i \le 10^9$), oddzielonych spacjami.

Wyjście

Wypisz pojedynczą liczbę całkowitą — maksymalną liczbę segmentów, na które można podzielić daną sekwencję.

Podzadania

To zadanie zawiera pięć podzadań z dodatkowymi ograniczeniami:

1. $1 \le N \le 20$, $a_i \le 10^6$. Liczba punktów: 13.
2. $1 \le N \le 500$. Liczba punktów: 14.
3. $1 \le N \le 3000$. Liczba punktów: 10.
4. $1 \le N \le 10^5$. Liczba punktów: 36.
5. Oryginalne ograniczenia. Liczba punktów: 27.

Przykład

Wejście 1

4
2 3 1 7

Wyjście 1

3

Wejście 2

5
6 2 3 9 13

Wyjście 2

3

Wejście 3

3
3 1 2

Wyjście 3

2