CF1628A Meximum Array

题目描述

Mihai 刚刚学会了 [MEX](https://en.wikipedia.org/wiki/Mex_(mathematics)) 的概念,并且非常喜欢,于是他决定马上用起来。 给定一个长度为 $n$ 的非负整数数组 $a$,Mihai 想要按照如下方式构造一个新数组 $b$: 当 $a$ 非空时,重复以下操作: - 选择一个整数 $k$($1 \leq k \leq |a|$)。 - 将数组 $a$ 的前 $k$ 个数的 MEX 值追加到数组 $b$ 的末尾,并从数组 $a$ 中删除这 $k$ 个数,剩余的数向前移动。 由于 Mihai 喜欢尽可能大的数组,他希望新数组 $b$ 在字典序上最大。因此,Mihai 想让你告诉他,按照最优构造方式,可以得到的字典序最大的数组 $b$ 是什么。 如果在第一个不同的位置 $x_i > y_i$,则数组 $x$ 字典序大于数组 $y$;或者当 $|x| > |y|$ 且 $y$ 是 $x$ 的前缀时(其中 $|x|$ 表示数组 $x$ 的长度)。 一个非负整数集合的 MEX 是不在该集合中的最小非负整数。例如,MEX($\{1, 2, 3\}$) $= 0$,MEX($\{0, 1, 2, 4, 5\}$) $= 3$。

输入格式

输入的第一行包含一个整数 $t$($1 \leq t \leq 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$ 的长度,接着输出 $b$ 数组的 $m$ 个元素。

说明/提示

在第一个测试用例中,字典序最大的数组 $b$ 是选择 $k=5$,即取整个数组 $a$ 的 MEX。这样得到的数组 $b$ 的首项最大,因为以更小的数开头的数组字典序更小,选择 $k