CFCF2185C.Shifted MEX

普及-

通过率：0%

AC君温馨提醒

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

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$ 。你可以执行下面的操作一次：

例如，如果 $a = [1, 3, 4, 2]$ ，你选择 $x = 3$ 进行操作，则 $a$ 变为 $[4, 6, 7, 5]$ 。

请输出操作后，数组 $a$ 的 $\operatorname{MEX}(a)^{\ast}$ 的最大可能值。

$\ast$ $\operatorname{MEX}(a)$ 表示数组中未出现的最小非负整数。例如， $\operatorname{MEX}([1, 2, 0, 5]) = 3$ ， $\operatorname{MEX}([1, 2, 4, 9]) = 0$ 。

输入的第一行为一个整数 $t$ $(1 \leq t \leq 1000)$ ，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(1 \le n \le 3000)$ ，表示数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(-10^9 \le a_i \le 10^9)$ ，表示数组 $a$ 。

保证所有测试用例中 $n$ 之和不超过 $3000$ 。

对于每个测试用例，输出执行一次操作后 $\operatorname{MEX}(a)$ 的最大可能值。

输入#1

6
1
4
5
0 1 1 2 3
2
1 1
4
4 2 3 6
5
2 4 1 0 -1
6
-1 1 2 3 5 6

输出#1

对于第一个测试用例，可以选择 $x = -4$ ，此时 $a = [0]$ ， $\operatorname{MEX}([0]) = 1$ 。

对于第二个测试用例， $\operatorname{MEX}$ 已经是 $4$ ，已是最大值，因此可以选择 $x = 0$ 不进行任何变化。