Longest Increasing Subsequence

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

5
-2 0 10 -10 -7 

3

Example 2

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

6