Longest Increasing Subsequence

Given an array of integer numbers ~x_1, x_2, \dots, x_n~, what is the length of the longest (strictly) increasing subsequence? Subsequence.

(Yes i'm lazy i wrote this problem statement 11.46 last night.)

Input

The first line contains an integer ~n~. The second line contains ~n~ integers, the values of the array.

Output

The length of the longest strictly increasing subsequence.

(If you've solved this problem before, try with a Segment Tree. I think its pretty intuitive :)

Constraints

• ~1 \le n \le 10^5~
• ~-10^9 \le x_i \le 10^9

Example 1

Input

5
-2 0 10 -10 -7

Output

3

Example 2

Input

10
-3 3 -2 0 3 4 9 3 -2 7

Output

6