6650: 最长上升子序列 II
[Creator : ]
Description
给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。
不用怀疑，本题和 4282 是一摸一样的。但是数据范围扩大了。
标准的 LIS 时间复杂度为 $O(N^2)$，而本题数据范围扩大到了 $10^5$。
不用怀疑，本题和 4282 是一摸一样的。但是数据范围扩大了。
标准的 LIS 时间复杂度为 $O(N^2)$，而本题数据范围扩大到了 $10^5$。
Input
第一行包含整数 $N$。
第二行包含 $N$ 个整数，表示完整序列。
第二行包含 $N$ 个整数，表示完整序列。
Output
输出一个整数，表示最大长度。
Constraints
$1≤N≤100,000$，
$-10^9≤$ 数列中的数 $≤10^9$
$-10^9≤$ 数列中的数 $≤10^9$
Sample 1 Input
7
3 1 2 1 8 5 6
Sample 1 Output
4
LCS 为 $1,2,5,6$
Sample 2 Input
10
-5 -1 8 -4 3 -2 -5 -6 2 -6
Sample 2 Output
4