g6-07895. 最长上升子序列·二分 未做

给定长度为 $n$ 的整数数组 $a_1,\dots ,a_n$，求最长严格上升子序列的长度。

本题 $n$ 可达 $10^5$，$O(n^2)$ 的做法会超时，需要使用 $O(n\log n)$ 的二分做法。

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

一行一个整数，表示最长严格上升子序列的长度。

输入 1

8
10 9 2 5 3 7 101 18

输出 1

4

$1\le n\le 10^5$，$1\le a_i\le 10^9$。