← 返回题目列表

Codeforces · 2160/A

A. MEX 分区

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

让 分区 多重集 $$$B$$$ 的 是多重集 $$$s_1, s_2,\ldots, s_k$$$ 的集合,使得每个元素在 $$$B$$$ 中以及所有 $$$s_1,s_2,\ldots,s_k$$$ 中出现相同的次数。

例如,$$$\{1,2,3,3\}$$$ 的某些分区包括 $$$\{1,3\}+\{2,3\}、\{1,2,3,3\}$$$ 和 $$$\{2\}+\{1,3\}+\{3\}$$$,但不包括$$$\{1,2\}+\{3\}$$$。

一个分区被称为 有效 如果分区中所有多重集的 $$$\operatorname{mex}$$$$$$^{\text{*}}$$$ 相同。的 有效分区的 分数 是分区中任何多重集的 $$$\operatorname{mex}$$$。

给您一个大小为 $$$n$$$ 的多重集 $$$A$$$。找到 最小值 分数 $$$A$$$ 的所有有效分区。

$$$^{\text{*}}$$$整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的最小排除 (MEX) 被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

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

第二行包含 $$$n$$$ 整数 $$$A_1, A_2, \ldots, A_n$$$ 表示 $$$A$$$ 的元素 ($$$0 \leq A_i \leq 100$$$)。

这是 不保证 元素按非降序给出。

输出

对于每个测试用例,输出最小值 分数 所有有效分区。

示例

输入
复制

2
3
0 0 0
2
1 2

输出
复制

1
0

注意

在第一个测试用例中,通过分区$$$\{0\}+\{0\}+\{0\}$$$可以获得$$$1$$$的最低分数。该分区是有效的,因为每个多重集的 $$$\operatorname{mex}$$$ 为 $$$1$$$,因此它是分区的分数。

在第二个测试用例中,我们可以使用 $$$\{1,2\}$$$ 作为分区中唯一的多重集,其中 $$$\operatorname{mex} 0$$$。