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.

Input Specification

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.

Output Specification

A single integer, the length of the array's longest increasing subsequence.

Sample Input 1

5
4 40 100 2 3

Sample Output 1

3

Sample Input 2

5
5 4 3 2 1

Sample Output 2

1