Desde que los primeros vikingos llegaron a la quebrada sagrada y se mezclaron con el antiguo linaje inca, la Estirpe de Björn mantiene vivo un único ritual: el del Guardián de la Barba Eterna. Es un cargo que pasa de generación en generación, y quien lo lleva tiene prohibido cortarse la barba jamás, pues se cree que los Annunaki dejaron su nave programada para reconocer el crecimiento continuo de una barba nunca cortada como la llave de su despertar.

Cada vez que el Guardián actual se acerca a la nave dormida, los sacerdotes tallan una nueva estela de piedra en la ladera de la montaña, registrando en orden el largo de su barba medido ese día. Las estelas quedan talladas en el orden exacto en que ocurrieron esas visitas: están fijas en la roca y nadie puede moverlas ni reordenarlas. Como el Guardián a veces se pareja las puntas para mantenerla prolija, el largo registrado no crece de forma perfecta: sube y baja de visita en visita.

La nave solo terminará de despertar si alguien logra leer, respetando el orden en que están talladas las estelas en la ladera, una secuencia de largos de barba estrictamente creciente.

La primera línea contiene un entero \(N\) (\(1 \le N \le 5 \times 10^4\)): la cantidad de estelas talladas.

La segunda línea contiene \(N\) enteros \(H_1, H_2, \ldots, H_N\) (\(1 \le H_i \le 10^9\)): el largo de barba registrado en la estela \(i\)-ésima, en el orden en que fue tallada.

Imprime un único entero: la longitud de la subsecuencia estrictamente creciente más larga de \(H\).

Explicación del ejemplo 1

Una senda válida es 2, 3, 6, 9, correspondiente a las estelas en las posiciones 2, 5, 6 y 7. No existe ninguna subsecuencia estrictamente creciente de longitud 5.

Explicación del ejemplo 2

Como se exige crecimiento estricto, dos estelas con el mismo largo nunca pueden formar parte de la misma secuencia.