Longest Increasing Subsequence

Hard#dynamic-programming #binary-search· solved by 0 · time limit 2.0 s

Find the length of the longest strictly increasing subsequence. $O(n^2)$ DP works for small $n$ ; the patience-sorting trick with binary search is $O(n \log n)$ .

Input

$n$ , then $n$ integers.

Output

The LIS length.

Constraints

$1 \le n \le 10^5$

Sample 1

Input

8
10 9 2 5 3 7 101 18

Output

Sample 2

Input

3
7 7 7

Output