Longest Increasing Subsequence

Given a sequence of length N, find the length of the longest strictly increasing subsequence.

Input Format

The first line contains an integer N.

The second line contains N integers, representing the complete sequence.

Output Format

Output an integer representing the maximum length.

Constraints

1 ≤ N ≤ 100000

-10⁹ ≤ Sequence elements ≤ 10⁹

Sample Input

7
3 1 2 1 8 5 6

Sample Output

4