Source : Northeastern Europe 2002, Far-Eastern Subregion
Description

A numeric sequence of ai is ordered if $a_1 < a_2 < ... < a_N$. Let the subsequence of the given numeric sequence $(a_1, a_2, ..., a_N)$be any sequence $(a_{i1}, a_{i2}, ..., a_{iK})$, where $1 <= i_1 < i_2 < ... < i_K <= N$. For example, sequence $(1, 7, 3, 5, 9, 4, 8)$ has ordered subsequences, e. g., $(1, 7), (3, 4, 8)$ and many others. All longest ordered subsequences are of length $4$, e. g., $(1, 3, 5, 8)$.
Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence $N$. The second line contains the elements of sequence - $N$ integers in the range from $0$ to $10000$ each, separated by spaces. $1 <= N <= 1000$.

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input
Sample Output