B. Игра в последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тёма и Вика играют в следующую игру.

Сперва Вика придумывает последовательность натуральных чисел $$$a$$$ длины $$$m$$$ и выписывает её на листочек. Затем она берёт новый листочек и выписывает на него последовательность $$$b$$$ по следующему правилу:

  • Сначала выписывается $$$a_1$$$
  • Затем только такие $$$a_i$$$ ($$$2 \le i \le m$$$), что $$$a_{i - 1} \le a_i$$$, обозначим длину этой последовательности как $$$n$$$.

Так, например из последовательности $$$a=[4, 3, 2, 6, 3, 3]$$$, Вика получит последовательность $$$b=[4, 6, 3]$$$.

После чего она отдаёт листочек с последовательностью $$$b$$$ Тёме. Он в свою очередь пытается угадать последовательность $$$a$$$.

Тёма считает победу в такой игре очень маловероятной, но всё же хочет найти хотя бы одну последовательность $$$a$$$, которая могла бы быть изначально загадана Викой. Помогите ему и выведите любую такую последовательность.

Обратите внимание, что длина выводимой вами последовательности не должна превышать последовательность из входных данных более, чем в два раза.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина последовательности $$$b$$$.

Во второй строке набора содержатся $$$n$$$ натуральных чисел $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — элементы последовательности.

Cумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите две строки. В первой из них выведите одно натуральное число $$$m$$$ — длину последовательности ($$$n \le m \le 2 \cdot n$$$). Во второй строке выведите $$$m$$$ натуральных чисел $$$a_1, a_2, a_3, \dots, a_m$$$ ($$$1 \le a_i \le 10^9$$$) — предполагаемая последовательность, которую Вика могла записать на первом листочке.

Если существует несколько подходящих последовательностей, вы можете вывести любую из них.

Пример
Входные данные
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
Выходные данные
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
Примечание

Первый пример разобран в условии.

Во втором примере, Вика могла загадать исходную последовательность.