A16485 | $Shifted MEX$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。你可以执行下面的操作一次： - 选择一个整数 $x$（可以为负数），对于每一个 $i$ $(1 \leq i \leq n)$，将 $a_i$ 变为 $a_i + x$。 例如，如果 $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

C++ 编辑器

输入

输出