Nuestro pequeño Askhat notó un fenómeno interesante: intentar cubrir un arreglo con "saltos" de sumas cada vez mayores puede no ser tan simple como parece. Por supuesto, ahora necesitas encontrar una manera de hacerlo.

Se te da una secuencia de números enteros positivos de longitud $N$.

Divide la secuencia dada en el número máximo de segmentos de tal manera que:

1. Cada elemento de la secuencia pertenezca exactamente a un segmento.
2. La suma de los números en cada segmento, excepto en el primero, no sea menor que la del anterior.

Entrada

La primera línea de la entrada contiene el entero $N$ ($1 \le N \le 5 \cdot 10^5$). La siguiente línea contiene $N$ enteros positivos $a_i$ ($1 \le a_i \le 10^9$), separados por espacios.

Salida

Imprime un solo entero: el número máximo de segmentos en los que se puede dividir la secuencia dada.

Subtareas

Esta tarea contiene cinco subtareas, con restricciones adicionales:

1. $1 \le N \le 20$, $a_i \le 10^6$. Puntuación: 13 puntos.
2. $1 \le N \le 500$. Puntuación: 14 puntos.
3. $1 \le N \le 3000$. Puntuación: 10 puntos.
4. $1 \le N \le 10^5$. Puntuación: 36 puntos.
5. Restricciones originales. Puntuación: 27 puntos.

Ejemplos

Entrada 1

4
2 3 1 7

Salida 1

3

Entrada 2

5
6 2 3 9 13

Salida 2

3

Entrada 3

3
3 1 2

Salida 3

2