CF340D Bubble Sort Graph

Iahub 最近学习了冒泡排序，这是一种用于将 $n$ 个元素 $a_{1}$、$a_{2}$、...、$a_{n}$ 的排列升序排序的算法。他已经厌倦了这个如此简单的算法，于是他发明了自己的图。这张图（我们称之为 $G$）最开始有 $n$ 个顶点且没有边。在执行冒泡排序的过程中，边的出现方式如下伪代码所描述。 ```plain procedure bubbleSortGraph() 建立一个有 n 个顶点且没有边的图 G 重复执行 swapped = false 对于 i = 1 到 n - 1（包含两端）做： 如果 a[i] > a[i + 1] 则 在 G 中添加一条无向边，连接顶点 a[i] 和 a[i + 1] 交换 a[i] 和 a[i + 1] 的值 swapped = true 结束如果 结束循环 直到 swapped 为假 /* 只要 swapped 为真，就持续执行本算法。*/ end procedure ``` 对于一张图，独立集是指这样的一组顶点：集合内任意两个顶点之间都没有边（即这些顶点之间没有相连的边）。最大独立集是指在所有独立集里，元素数量最多的集合。给定一个排列，如果我们使用该排列作为 bubbleSortGraph 中的排列 $a$，请你求出图 $G$ 的最大独立集的大小。

输入的第一行包含一个整数 $n$（$2 \le n \le 10^{5}$）。 第二行包含 $n$ 个互不相同的整数 $a_{1}$、$a_{2}$、...、$a_{n}$（$1 \le a_{i} \le n$）。

输出一个整数，表示问题的答案。

考虑第一个样例。冒泡排序会交换元素 3 和 1。我们在图中添加一条边 $(1, 3)$。此时排列变为 $[1, 3, 2]$。接着冒泡排序交换元素 3 和 2。我们再加一条边 $(2, 3)$。此时排列已排序完毕。我们得到了一个有 3 个顶点和 2 条边（$(1, 3)$ 和 $(2, 3)$）的图。它的最大独立集是 $[1, 2]$。 由 ChatGPT 5 翻译