G. Восстанови перестановку
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность из $$$n$$$ чисел называется перестановкой, если она содержит в себе все числа от $$$1$$$ до $$$n$$$ ровно по одному разу. Например, последовательности [$$$3, 1, 4, 2$$$], [$$$1$$$] и [$$$2,1$$$] являются перестановками, а [$$$1,2,1$$$], [$$$0,1$$$] и [$$$1,3,4$$$] — нет.

Для перестановки $$$p$$$ чётной длины $$$n$$$ можно получить массив $$$b$$$ длины $$$\frac{n}{2}$$$ такой, что:

  • $$$b_i = \max(p_{2i - 1}, p_{2i})$$$ для $$$1 \le i \le \frac{n}{2}$$$

Например, если $$$p$$$ = [$$$2, 4, 3, 1, 5, 6$$$], то:

  • $$$b_1 = \max(p_1, p_2) = \max(2, 4) = 4$$$
  • $$$b_2 = \max(p_3, p_4) = \max(3,1)=3$$$
  • $$$b_3 = \max(p_5, p_6) = \max(5,6) = 6$$$
Итого получим $$$b$$$ = $$$[4, 3, 6]$$$.

Для заданного массива $$$b$$$ найдите лексикографически минимальную перестановку $$$p$$$ такую, что из неё можно получить заданный массив $$$b$$$.

Если $$$b$$$ = [$$$4,3,6$$$], то лексикографически минимальная перестановка, из которой можно его получить, это $$$p$$$ = [$$$1,4,2,3,5,6$$$], так как:

  • $$$b_1 = \max(p_1, p_2) = \max(1, 4) = 4$$$
  • $$$b_2 = \max(p_3, p_4) = \max(2, 3) = 3$$$
  • $$$b_3 = \max(p_5, p_6) = \max(5, 6) = 6$$$

Перестановка $$$x_1, x_2, \dots, x_n$$$ лексикографически меньше перестановки $$$y_1, y_2 \dots, y_n$$$, если и только если существует такое $$$i$$$ ($$$1 \le i \le n$$$), что $$$x_1=y_1, x_2=y_2, \dots, x_{i-1}=y_{i-1}$$$ и $$$x_i<y_i$$$.

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

Первая строка входных данных содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

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

Вo второй строке каждого набора входных данных записано ровно $$$\frac{n}{2}$$$ целых чисел $$$b_i$$$ ($$$1 \le b_i \le n$$$) — элементы массива $$$b$$$.

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

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

Для каждого набора входных данных выведите в отдельной строке:

  • лексикографически минимальную перестановку $$$p$$$ такую, что из неё можно получить массив $$$b$$$;
  • или число -1, если искомой перестановки не существует.
Пример
Входные данные
6
6
4 3 6
4
2 4
8
8 7 2 3
6
6 4 2
4
4 4
8
8 7 4 5
Выходные данные
1 4 2 3 5 6 
1 2 3 4 
-1
5 6 3 4 1 2 
-1
1 8 6 7 2 4 3 5
Примечание

Первый набор входных данных разобран в условии задачи.