L. Towers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

In one line, output the number – sequence beauty of Veronica's towers.

Examples
Input
5
1 3 5 2 4
Output
3
Input
7
10 1 5 2 6 3 4
Output
4