310626: CF1862B. Sequence Game

B. Sequence Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Tema and Vika are playing the following game.

First, Vika comes up with a sequence of positive integers $a$ of length $m$ and writes it down on a piece of paper. Then she takes a new piece of paper and writes down the sequence $b$ according to the following rule:

• First, she writes down $a_1$.
• Then, she writes down only those $a_i$ ($2 \le i \le m$) such that $a_{i - 1} \le a_i$. Let the length of this sequence be denoted as $n$.

For example, from the sequence $a=[4, 3, 2, 6, 3, 3]$, Vika will obtain the sequence $b=[4, 6, 3]$.

She then gives the piece of paper with the sequence $b$ to Tema. He, in turn, tries to guess the sequence $a$.

Tema considers winning in such a game highly unlikely, but still wants to find at least one sequence $a$ that could have been originally chosen by Vika. Help him and output any such sequence.

Note that the length of the sequence you output should not exceed the input sequence length by more than two times.

Input

Each test consists of multiple test cases. The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. This is followed by a description of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the sequence $b$.

The second line of each test case contains $n$ integers $b_1, b_2, b_3, \dots, b_n$ ($1 \le b_i \le 10^9$) — the elements of the sequence.

The sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output two lines. In the first line, output a single integer $m$ — the length of the sequence ($n \le m \le 2 \cdot n$). In the second line, output $m$ integers $a_1, a_2, a_3, \dots, a_m$ ($1 \le a_i \le 10^9$) — the assumed sequence that Vika could have written on the first piece of paper.

If there are multiple suitable sequences, you can output any of them.

ExampleInput

6
3
4 6 3
3
1 2 3
5
1 7 9 5 7
1
144
2
1 1
5
1 2 2 1 1

Output

6
4 3 2 6 3 3
3
1 2 3
6
1 7 9 3 5 7
1
144
2
1 1
6
1 2 2 1 1 1

Note

The first sample is explained in the problem statement.

In the second sample, Vika could have chosen the original sequence.

题目大意：
Tema和Vika在玩一个游戏。Vika首先想出一个长度为m的正整数序列a，并将其写在一张纸上。然后她再拿出一张新纸，根据以下规则写下序列b：
1. 首先，她写下a1。
2. 然后，她只写下那些ai（2≤i≤m），使得ai-1≤ai。设这个序列的长度为n。
例如，从序列a=[4, 3, 2, 6, 3, 3]，Vika将得到序列b=[4, 6, 3]。
然后，她将带有序列b的纸条给Tema。Tema试图猜测序列a。
Tema认为赢得这样的游戏的可能性非常小，但他仍然想找到至少一个可能最初被Vika选择的序列a。帮助他，并输出这样一个序列。
注意，您输出的序列长度不应超过输入序列长度的两倍。

输入数据格式：
每个测试用例由多个测试组成。输入数据的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——序列b的长度。
每个测试用例的第二行包含n个整数b1,b2,b3,…,bn（1≤bi≤10^9）——序列的元素。
所有测试用例的n值之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出两行。在第一行，输出一个整数m——序列的长度（n≤m≤2×n）。在第二行，输出m个整数a1,a2,a3,…,am（1≤ai≤10^9）——Vika可能写在第一张纸上的假定序列。
如果有多个合适的序列，您可以输出其中任何一个。题目大意： Tema和Vika在玩一个游戏。Vika首先想出一个长度为m的正整数序列a，并将其写在一张纸上。然后她再拿出一张新纸，根据以下规则写下序列b： 1. 首先，她写下a1。 2. 然后，她只写下那些ai（2≤i≤m），使得ai-1≤ai。设这个序列的长度为n。 例如，从序列a=[4, 3, 2, 6, 3, 3]，Vika将得到序列b=[4, 6, 3]。 然后，她将带有序列b的纸条给Tema。Tema试图猜测序列a。 Tema认为赢得这样的游戏的可能性非常小，但他仍然想找到至少一个可能最初被Vika选择的序列a。帮助他，并输出这样一个序列。 注意，您输出的序列长度不应超过输入序列长度的两倍。 输入数据格式： 每个测试用例由多个测试组成。输入数据的第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——序列b的长度。 每个测试用例的第二行包含n个整数b1,b2,b3,…,bn（1≤bi≤10^9）——序列的元素。 所有测试用例的n值之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出两行。在第一行，输出一个整数m——序列的长度（n≤m≤2×n）。在第二行，输出m个整数a1,a2,a3,…,am（1≤ai≤10^9）——Vika可能写在第一张纸上的假定序列。 如果有多个合适的序列，您可以输出其中任何一个。