$1 \le n \le 10 ^ 5$

这个题要求的是第 $i$ 发导弹不能高于第 $i - 1$ 发，也就是说，我们的导弹的高度是单调不升的，我们最多能拦截的导弹怎么算呢？最少用几套系统拦截呢？

对于第一问来说，我们将视角反转过来，看从末尾开始，每次导弹的高度都要大于等于上一次的，最多能打几个，那么这就是一个简单的 LIS 问题，那么我们求的就是非严格上升的最长子序列。

对于这类问题我们采用的方式常见的就是 $\mathcal{O}(n ^ 2)$ 的 DP，但是这个题的复杂度不允许，我们用另一种形式，我们定义 $f_i$ 表示长度为 $i$ 结尾的这样的上升子序列，结尾最短的值，那么我们发现这个值在 $f$ 中一定是单调的，我们考虑维护这个 $f$ 数组。

如果当前的 $a_i > f_t$，那么说明当前的 $a_i$ 只能接到 $f$ 的后面，无法对之前的造成任何有益的贡献。

如果当前的 $a_i \le f_t$，那么说明当前的 $a_i$ 虽然不能接到 $f$ 的后面，但是可以对之前更短的 $f$ 产生一个更优的贡献，我们只需要找到第一个大于 $a_i$ 的位置的 $f_j$，直接 $f_j \to a_i$ 即可。

然后对于第二问来说，这是一个很著名的定理，叫做 **Dilworth 定理**，这个定理的内容是这样的：

对于一个偏序集 $S$ 上的偏序 $\preceq$，称 $S$ 的全序子集为 **链**。若 $S$ 的子集 $T$ 中任意两个不同的元素均不可比则我们称 $T$ 为反链。

说人话就是，现在有一个全集 $S$，从中选出若干个元素，组成一个集合，这个集合按一种特殊的偏序的关系，则这个集合 $S$ 中的任意两个元素都能进行比较，则这个子集称为**链**。若有个子集 $T$，对于这个集合中的任意选出的两个元素，都无法按照这种偏序关系比较，那么称这个子集 $T$ 为**反链**。

需要注意的是这个偏序关系 $\preceq$ 来说，其可能是一种比较方式，就是钦定的一种规则，例如，当 $a \le b$ 时我们称其为可比，那么我们拿出来的如果是 $a > b$ 就是不可比。

我们设 $(S, \preceq)$ 为一个有限偏序集，则：

- 最小链覆盖数 = 最大反链长度

- 最小反链覆盖数 = 最大链长度

那我们这个题就可以直接做了，我们对于 $\ge$ 的偏序关系来说，其反就是 $<$，就是严格的小于，那么我们求严格最长上升的长度就是答案。