David's Exquisite Subsequence
David's enterprising sloth has created an array of its own. David thinks it is a most exquisite array and wants to enter it into "Git's Next Most Increasing Array" - an exciting reality TV show where contestants enter their arrays. The winning array has the longest increasing subsequence.
Before entering his Sloth's (Jeff's) array, he wants to know what it's longest increasing subsequence is.
The first line contains an integer \(n\) \((1 \leq n \leq 10^4)\), the length of Jeff's array.
The next line contains \(n\) space-separated integers. The i-th integer \(x_i\) \((1 \leq x_i \leq 10^6)\) is the i-th element of the array.
A single integer, the length of the array's longest increasing subsequence.
Sample Input 1
5 4 40 100 2 3
Sample Output 1
Sample Input 2
5 5 4 3 2 1
Sample Output 2