Longest Increasing Subsequence

Given an integer array A of length N, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence that ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌‌​​‌‌​​‌‌​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌​​‌​​‌‌​​​​‌​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​​‌​​‌‌‌​​‌can be derived from an array by deleting zero or more elements without changing the relative order of the remaining elements.

---

Input Format

• Line 1: An integer N (1 ≤ N ≤ 100,000).
• Line 2: N space-separated integers A[0], A[1], ..., A[N-1] (-10^9 ≤ A[i] ≤ 10^9).

---

Output Format

• Print a single integer ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌‌​​‌‌​​‌‌​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌​​‌​​‌‌​​​​‌​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​​‌​​‌‌‌​​‌representing the length of the longest strictly increasing subsequence.

---

Example 1

Input:

8
10 9 2 5 3 7 101 18

Output:

4

Explanation: The longest strictly increasing subsequence is [2, 3, 7, 101] (or [2, 5, 7, 101]), which has length 4.

---

Example 2

Input:

​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌‌​​‌‌​​‌‌​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌​​‌​​‌‌​​​​‌​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​​‌​​‌‌‌​​‌6
0 1 0 3 2 3

Output:

4

Explanation: The longest strictly increasing subsequence is [0, 1, 2, 3] with length 4. ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌‌​​‌‌​​‌‌​​‌‌‌​​‌​‌‌​​‌​‌​​‌‌‌​​‌​​‌‌​​‌​​‌‌​​​​‌​​‌‌​​‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​​‌​​‌‌‌​​‌

8
10 9 2 5 3 7 101 18

4

6
0 1 0 3 2 3

4