CF2135A Against the Difference

我们定义一个“块”为一个数组，其中所有元素均等于该数组的长度。例如，$[3, 3, 3]$，$[1]$ 和 $[4, 4, 4, 4]$ 都是块，而 $[1, 1, 1]$ 和 $[2, 3, 3]$ 不是块。 如果一个数组可以通过任意多个块（可以为零个块）的拼接得到，则称该数组为“整洁的”。注意，空数组也视为整洁的。 给定一个由 $n$ 个整数构成的数组 $a$。请你求出其最长整洁子序列的长度$^{\text{∗}}$。 $^{\text{∗}}$ 如果序列 $c$ 可以通过从序列 $a$ 中删除若干（可以为零或全部）任意位置的元素得到，则称 $c$ 是 $a$ 的一个子序列。

每组测试包含若干组数据。第一行为测试组数 $t$，$1 \leq t \leq 10^4$。接下来是每组测试数据。 每组测试数据的第一行为一个整数 $n$，$1 \leq n \leq 2\cdot10^5$，表示数组 $a$ 的长度。 第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$，$1 \leq a_i \leq n$，表示数组 $a$ 的元素。 保证所有测试数据的 $n$ 之和不超过 $2\cdot10^5$。

对于每组测试数据，输出一个整数，表示数组 $a$ 的最长整洁子序列的长度。

在第一个测试用例中，整个数组 $[1]$ 本身是整洁的，因为它本身就是一个块。 在第二个测试用例中，整个数组 $[2, 2]$ 本身是整洁的，因为它本身就是一个块。 在第三个测试用例中，整个数组 $[2,2,1,1]$ 本身是整洁的，因为它可以拆成三个块：$[2,2]$、$[1]$ 和 $[1]$。 在第四个测试用例中，$a$ 的一个最长整洁子序列是 $[1, 3, 3, 3, 1]$。 在第五个测试用例中，最长整洁子序列为空。 由 ChatGPT 5 翻译