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


Submitting to 'Longest Increasing Subsequence'


You're not logged in! Click here to login


Submitting to 'Longest Increasing Subsequence'


You're not logged in! Click here to login


Submitting .cpp to 'Longest Increasing Subsequence'


You're not logged in! Click here to login

Time Limit: 2.5 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: Classic problem

Subtask Score
1 0
2 47
3 53