Meximum Array

题意翻译

小 A 有一个长度为 $n$ 的数组 $a$ 和一个初始为空的数组 $b$。小 A 可以执行若干次如下操作直到 $a$ 数组为空为止： - 选择一个整数 $k(1\leqslant k\leqslant |a|)$，其中 $|a|$ 为当前 $a$ 数组的长度。 - 取出 $a$ 数组的前 $k$ 个元素，将这些元素的 MEX 值放入 $b$ 数组的末尾，并将 $a$ 数组中剩余的元素提到前面，最后删除前面取出的 $k$ 个元素。其中一个由非负整数组成的集合的 MEX 值为最小的未在集合中出现的**非负整数**。 小 A 希望最终得到的 $b$ 数组的字典序越大越好。请你求出这个可能的字典序最大的 $b$ 数组。数组 $x$ 的字典序大于数组 $y$，当且仅当数组 $y$ 是数组 $x$ 的前缀，或者存在一个位置 $p$，使得 $\forall i\in[1,p)$，$x_i=y_i$ 且 $x_p>y_p$。 数组范围： - $t$ 组数据，$1\leqslant t\leqslant 100$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $0\leqslant a_i\leqslant n$。 Translated by Eason_AC 2022.1.25

题目描述

Mihai has just learned about the [MEX](https://en.wikipedia.org/wiki/Mex_(mathematics)) concept and since he liked it so much, he decided to use it right away. Given an array $ a $ of $ n $ non-negative integers, Mihai wants to create a new array $ b $ that is formed in the following way: While $ a $ is not empty: - Choose an integer $ k $ ( $ 1 \leq k \leq |a| $ ). - Append the MEX of the first $ k $ numbers of the array $ a $ to the end of array $ b $ and erase them from the array $ a $ , shifting the positions of the remaining numbers in $ a $ . But, since Mihai loves big arrays as much as the MEX concept, he wants the new array $ b $ to be the lexicographically maximum. So, Mihai asks you to tell him what the maximum array $ b $ that can be created by constructing the array optimally is. An array $ x $ is lexicographically greater than an array $ y $ if in the first position where $ x $ and $ y $ differ $ x_i > y_i $ or if $ |x| > |y| $ and $ y $ is a prefix of $ x $ (where $ |x| $ denotes the size of the array $ x $ ). The MEX of a set of non-negative integers is the minimal non-negative integer such that it is not in the set. For example, MEX({ $ {1, 2, 3} $ }) $ = 0 $ and MEX({ $ {0, 1, 2, 4, 5} $ }) $ = 3 $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of elements in the array $ a $ . The second line of each test case contains $ n $ non-negative integers $ a_1, \ldots, a_n $ ( $ 0 \leq a_i \leq n $ ), where $ a_i $ is the $ i $ -th integer from the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case print $ m $ — the length of the maximum array $ b $ Mihai can create, followed by $ m $ integers denoting the elements of the array $ 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

说明

In the first test case, the lexicographically maximum array $ b $ is obtained by selecting $ k=5 $ , resulting in the $ MEX $ of the whole array $ a $ . It is lexicographically maximum because an array starting with a smaller number than $ 4 $ is lexicographically smaller, and choosing a $ k<5 $ would result in an array starting with a number smaller than $ 4 $ . In the second test case, there are two ways to obtain the maximum array: first selecting $ k=6 $ , then $ k=2 $ , or first selecting $ k=7 $ and then $ k=1 $ .