Longest Increasing Subsequence

This is a classic LIS problem. Given a sequence of N (1 ≤ N ≤ 1,000,000) numbers, output the length of the longest increasing subsequence.

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order (strictly increasing), lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous.

Input

The first line has an integer N, denoting the number of integers in the sequence. The next line contains N integers.

Output

Output the length of the longest increasing subsequence.

Sample Input

6
1 2 4 4 5 3

Sample Output

4