← 返回题目列表

Codeforces · 1406/A

A. 墨西哥子集

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

给定一组整数(它可以包含相等的元素)。

你必须将它分成两个子集 $$$A$$$ 和 $$$B$$$ (它们都可以包含相同的元素或为空)。你必须最大化 $$$mex(A)+mex(B)$$$ 的价值。

这里集合的 $$$mex$$$ 表示集合中不存在的最小非负整数。例如:

- $$$mex(\{1,4,0,2,2,1\})=3$$$
- $$$mex(\{3,3,2,1,3,0,0\})=4$$$
- $$$mex(\varnothing)=0$$$ ($$$mex$$$ 为空集)

如果对于任何整数 $$$x$$$,$$$x$$$ 在该集合中出现的次数等于 $$$x$$$ 在 $$$A$$$ 中出现的次数与 $$$x$$$ 在 $$$B$$$ 中出现的次数之和,则该集合被分为两个子集 $$$A$$$ 和 $$$B$$$。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 100$$$) — 集合的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\dots a_n$$$ ($$$0\leq a_i\leq 100$$$) — 集合中的数字。

输出

对于每个测试用例,打印 $$$mex(A)+mex(B)$$$ 的最大值。

示例

输入 #1

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

输出 #1

5
3
4
0

注意

在第一个测试用例中,$$$A=\left\{0,1,2\right\},B=\left\{0,1,5\right\}$$$ 是一个可能的选择。

在第二个测试用例中,$$$A=\left\{0,1,2\right\},B=\varnothing$$$ 是一个可能的选择。

在第三个测试用例中,$$$A=\left\{0,1,2\right\},B=\left\{0\right\}$$$ 是一个可能的选择。

在第四个测试用例中,$$$A=\left\{1,3,5\right\},B=\left\{2,4,6\right\}$$$ 是一个可能的选择。