Dado un arreglo de \(n\) enteros, encuentra el largo de su subsecuencia estrictamente creciente más larga (se eligen elementos en su orden original, no necesariamente contiguos).

Con \(n = 10^5\) hace falta \(O(n \log n)\).

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\). La segunda tiene los \(n\) enteros, con \(|a_i| \le 10^9\).

Salida

El largo de la subsecuencia.

Ejemplo 1

Entrada

8
10 9 2 5 3 7 101 18

Salida

4

Ejemplo 2

Entrada

6
0 1 0 3 2 3

Salida

4

Ejemplo 3

Entrada

7
7 7 7 7 7 7 7

Salida

1