This is a classic LIS problem. Given a sequence of N (1 ≤ N ≤ 5,100) 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.


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


Output the length of the longest increasing subsequence.

Sample Input

1 2 4 4 5 3

Sample Output


Submitting .cpp to 'lis_easy'

You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 256MB
Your best score: 0
Source: Classic problem

Subtask Score
1 100
2 0