← 返回题目列表

Codeforces · 2185/C

C. 移动 MEX

中文机器翻译题面 查看原题

给你一个 $$$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]$$$。

执行运算后输出 $$$\operatorname{MEX}(a)$$$$$$^{\text{*}}$$$ 的最大可能值。

$$$^{\text{*}}$$$$$$\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)$$$ 的最大可能值。

示例

输入
复制

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
4
1
3
4
3

注意

对于第一个测试用例,使用 $$$x = -4$$$ 执行运算使得 $$$a = [0]$$$,并且 $$$\operatorname{MEX}([0]) = 1$$$。

对于第二个测试用例,$$$\operatorname{MEX}$$$ 已经是 $$$4$$$,这是可能的最高值,因此我们可以使用 $$$x = 0$$$ 执行操作,这不会更改数组。