Veronica likes to play with blocks, and she especially likes to build towers. Veronica always tries hard while building towers; she carefully builds them in one row.
This time she built $$$n$$$ towers, each of which had a height of $$$a_i$$$ blocks. After long and hard work, Veronica called her father. As a true connoisseur of art and a real mathematician, Igor has to value the beauty of all buildings at once. Igor thinks that the beauty of all the built in a row towers equals the longest increasing subsequence of their heights.
LIS (the Longest Increasing Subsequence) – is a subsequence where each next element is longer than previous one, so it is the following set of indexes $$$i_1 \ldots i_k$$$, that: $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$, $$$a[i_1] \lt a[i_2] \lt \ldots \lt a[i_k]$$$.
Veronica built quite a lot of towers, help Igor to determine the beauty of Veronica's towers.
In the first line is given an integer number $$$n$$$ $$$(1\leq n \leq 3 \cdot 10^5)$$$ – the amount of towers built by Veronica.
The next line consists of $$$n$$$ integer numbers $$$a_i$$$ $$$(1\leq a_i\leq 10^9, 1\leq i\leq n)$$$ separated by spaces – the height of towers.
In one line, output the number – sequence beauty of Veronica's towers.
5 1 3 5 2 4
3
7 10 1 5 2 6 3 4
4
| Name |
|---|


