Tenemos un arreglo que contiene ~n~ enteros. Su tarea es determinar la subsecuencia incremental más larga en el arreglo, es decir, aquella subsecuencia más larga donde cada elemento es más grande que el anterior. Una subsecuencia es una secuencia que puede derivarse del arreglo eliminando algunos elementos sin cambiar el orden de los elementos restantes.

Entrada

La primera línea contiene un entero ~n~: el tamaño del arreglo. En la línea siguiente, hay ~n~ enteros ~x_1, x_2, \ldots, x_n~: el contenido del arreglo.

Salida

Imprima la longitud de la subsecuencia incremental más larga.

Restricciones

• ~1 \leq n \leq 2 \cdot 10^5~
• ~1 \leq x_i \leq 10^9~

Ejemplo de Entrada

8
7 3 5 3 6 2 9 8

Ejemplo de Salida

4