Harddpsearcharrays
Longest Increasing Subsequence
Time limit 2 s · Memory 64 MBAcceptance: —Solved by: 0
Statement
The first line contains n, the second line contains n integers. Print the length of the longest strictly increasing subsequence. Its elements need not be adjacent in the array, but their order is preserved.
Examples
Example 1
Input
6 5 2 8 6 3 6
Output
3
Example 2
Input
8 10 9 2 5 3 7 101 18
Output
4
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a_i ≤ 10^9