Sequence Game
Contest: Codeforces Round 894 (Div. 3)
Difficulty rating: 800
Tags: constructive algorithms

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first sample is explained in the problem statement.

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

Example input:
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

Example 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

Editorial:
Let's compare each pair of adjacent numbers. If the left number is smaller than the right number, then the right number is at least $$$2$$$. We will insert $$$1$$$ between them.
Now, for each pair of numbers, it is true that either these two numbers were originally in the sequence, or one of them is $$$1$$$. In this case, if two numbers were originally in the sequence, then the left number is not smaller than the right number. If the left number is $$$1$$$, then it is smaller than the right number, since the right number was at least $$$2$$$. If the right number is $$$1$$$, then the left number in the pair is not smaller than the right number.
We have checked all cases. It is evident that such a sequence is valid, as Vika would have only removed all the $$$1$$$ we added and nothing more.