CF2135A.Against the Difference

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

我们定义一个“块”为一个数组，其中所有元素均等于该数组的长度。例如， $[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

6
1
1
2
2 2
4
2 2 1 1
6
1 2 3 3 3 1
8
8 8 8 8 8 8 8 7
10
2 3 3 1 2 3 5 1 1 7

输出#1

在第一个测试用例中，整个数组 $[1]$ 本身是整洁的，因为它本身就是一个块。

在第二个测试用例中，整个数组 $[2, 2]$ 本身是整洁的，因为它本身就是一个块。

在第三个测试用例中，整个数组 $[2,2,1,1]$ 本身是整洁的，因为它可以拆成三个块： $[2,2]$ 、 $[1]$ 和 $[1]$ 。

在第四个测试用例中， $a$ 的一个最长整洁子序列是 $[1, 3, 3, 3, 1]$ 。

在第五个测试用例中，最长整洁子序列为空。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?