Вероника любит играть в игры с кубиками, особенно ей нравится строить из них башенки. Вероника всегда очень усердно старается при постройке башенок, она аккуратно строит их в один ряд.
В этот раз она построила целых $$$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