Given an array of ~ N ~ integers ~ A_1, A_2, \ldots, A_N ~.

A strictly increasing subsequence is a sequence ~A_{i_1}, A_{i_2}, \ldots, A_{i_k} ~ that satisfies ~ i_1 < i_2 < \ldots < i_k ~ and ~ A_{i_1} < A_{i_2} < \ldots < A_{i_k}~ .

Requirement:

• Find the length of the longest strictly increasing subsequence of this array.

Input

• The first line contains a positive integer ~ N ~ ~( 1 \leq N \leq 5000 )~.
• The second line contains ~N~ integers ~ A_1, A_2, \ldots, A_N~ ~( 1 \leq A_i \leq 10^6 )~.

Output

• Print the length of the longest strictly increasing subsequence.

Sample Input

6
1 2 5 4 6 2

Sample Output

4