L. Башенки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вероника любит играть в игры с кубиками, особенно ей нравится строить из них башенки. Вероника всегда очень усердно старается при постройке башенок, она аккуратно строит их в один ряд.

В этот раз она построила целых $$$n$$$ башенок, каждая из которых имела $$$a_i$$$ высоту кубиков. После долгой и кропотливой работы, Вероника позвала папу. Игорю как истинному ценителю искусства и настоящему математику, необходимо определить красоту всех построек сразу. Игорь считает, что красота всех построенных в ряд башенок равняется наибольшей возрастающей подпоследовательности из их высот.

НВП (Наибольшая возрастающая подпоследовательность) - это такая последовательность, в которой каждый следующий элемент больше предыдущего, то есть это такой набор индексов $$$i_1 \ldots i_k$$$, что: $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$, $$$a[i_1] \lt a[i_2] \lt \ldots \lt a[i_k]$$$.

Вероника сделал очень много башенок, помогите определить Игорю красоту башенок Вероники.

Входные данные

В первой строке задано целое число $$$n$$$ $$$(1\leq n \leq 3 \cdot 10^5)$$$  — количество башенок, которые построила Вероника.

Далее в следующей строке содержатся $$$n$$$ целых чисел $$$a_i$$$ $$$(1\leq a_i\leq 10^9, 1\leq i\leq n)$$$, разделённых пробелами  — высоты башенок.

Выходные данные

В единственной строке выведите число – красоту последовательности башенок Вероники.

Примеры
Входные данные
5
1 3 5 2 4
Выходные данные
3
Входные данные
7
10 1 5 2 6 3 4
Выходные данные
4