← 返回题目列表

Codeforces · 1628/A

A. 最大数组

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

Mihai 刚刚了解了 MEX 概念,由于他非常喜欢它,所以他决定立即使用它。

给定一个包含 $$$n$$$ 非负整数的数组 $$$a$$$,Mihai 想要创建一个新数组 $$$b$$$,其形成方式如下:

当 $$$a$$$ 不为空时:

- 选择一个整数 $$$k$$$ ($$$1 \leq k \leq |a|$$$)。
- 将数组 $$$a$$$ 的前 $$$k$$$ 数字的 MEX 附加到数组 $$$b$$$ 的末尾,并将它们从数组 $$$a$$$ 中删除,移动 $$$a$$$ 中剩余数字的位置。

但是,由于 Mihai 和 MEX 概念一样喜欢大数组,因此他希望新数组 $$$b$$$ 成为字典顺序中的最大值。所以,Mihai 让你告诉他通过最优构造数组可以创建的最大数组 $$$b$$$ 是多少。

如果在第一个位置 $$$x$$$ 和 $$$y$$$ 不同 $$$x_i > y_i$$$ 或如果 $$$|x| ,则数组 $$$x$$$ 按字典顺序大于数组 $$$y$$$ > |y|$$$ 和 $$$y$$$ 是 $$$x$$$ 的前缀(其中 $$$|x|$$$ 表示数组 $$$x$$$ 的大小)。

一组非负整数的 MEX 是不在该集合中的最小非负整数。例如,MEX({$$${1, 2, 3}$$$}) $$$= 0$$$ 和 MEX({$$${0, 1, 2, 4, 5}$$$}) $$$= 3$$$。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 非负整数 $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_i \leq n$$$),其中 $$$a_i$$$ 是数组 $$$a$$$ 中的第 $$$i$$$ 个整数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$m$$$ — Mihai 可以创建的最大数组 $$$b$$$ 的长度,后跟 $$$m$$$ 整数,表示数组 $$$b$$$ 的元素。

示例

输入 #1

6
5
1 0 2 0 3
8
2 2 3 4 0 1 2 0
1
1
5
0 1 2 3 4
4
0 1 1 0
10
0 0 2 1 1 1 0 0 1 1

输出 #1

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

注意

在第一个测试用例中,通过选择 $$$k=5$$$ 获得按字典顺序排列的最大数组 $$$b$$$,从而得到整个数组 $$$a$$$ 的 $$$MEX$$$。它按字典顺序是最大的,因为以小于 $$$4$$$ 的数字开头的数组按字典顺序更小,并且选择 $$$k<5$$$ 将导致以小于 $$$4$$$ 的数字开头的数组。

在第二个测试用例中,有两种方法获得最大数组:先选择$$$k=6$$$,然后$$$k=2$$$,或者先选择$$$k=7$$$,然后$$$k=1$$$。