CF1628A.Meximum Array

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Mihai has just learned about the MEX 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

说明/提示

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$ .

首页