U593857 【模板】最长上升子序列

:::epigraph[——Ferm_Tawn] $\mathrm{O}(n \log n) \ \mathrm{only}!$ :::

给出一个长度为 $n$ 的数组 $a$ ，求出 $a$ 的最长上升子序列的长度。 ::::info[什么是 **最长上升子序列**]{open} 一个子序列 $b_1 , b_2 \dots b_k$ 被称为最长上升子序列当且仅当$b_i > b_{i-1} (2 \le i \le k)$ 且在原数组中是最长的。 ::::

输入共两行。 第一行一个整数 $n$。 第二行 $n$ 个整数 $a_1,a_2,\dots a_n$。

输出共一行。 第一行一个整数 $\mathrm{len}$ ，表示答案。

::cute-table{tuack} |$\mathrm{Subtask}$| 测试点编号 | $n \leq$ | $a_i \leq$ | 特殊性质 | |:-:| :-: | :-: | :-: | :-: | |$0$| $1, 2$ | $20$ | $100$ | 无 | |$1$| $3$ | $10^3$ | $10^4$ | AB | |^| $4,5$ | ^ | ^ | 无 | |$2$| $6 \sim 8$ | $3 \times 10^4$ | ^ | ^ | |^|$9 \sim 10$|^|$100$|^| |$3$| $11$ | $2.5 \times 10^5$ | ^ | A | |^| $12 \sim 14$ | ^ | $10^7$ | B | |^| $15$ | ^ | ^ | A | |^| $16 \sim 20$ | ^ | ^ | 无 | |$4$|$\mathrm{Hack}$|$2 \times 10^6$|^|^| 特殊性质 $\mathrm{A}$ : $a_i$ 在值域内随机生成。 特殊性质 $\mathrm{B}$ : $a_1,a_2,\dots a_n$ 互不相同。