CF1759G.Restore the Permutation

A sequence of $n$ numbers is called permutation if it contains all numbers from $1$ to $n$ exactly once. For example, the sequences [$3, 1, 4, 2$], [$1$] and [$2,1$] are permutations, but [$1,2,1$], [$0,1$] and [$1,3,4$] — are not.

For a permutation $p$ of even length $n$ you can make an array $b$ of length $\frac{n}{2}$ such that:

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

For example, if $p$ = [$2, 4, 3, 1, 5, 6$], then:

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

As a result, we made $b$ = $[4, 3, 6]$.

For a given array $b$, find the lexicographically minimal permutation $p$ such that you can make the given array $b$ from it.

If $b$ = [$4,3,6$], then the lexicographically minimal permutation from which it can be made is $p$ = [$1,4,2,3,5,6$], since:

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

A permutation $x_1, x_2, \dots, x_n$ is lexicographically smaller than a permutation $y_1, y_2 \dots, y_n$ if and only if there exists such $i$ ($1 \le i \le n$) that $x_1=y_1, x_2=y_2, \dots, x_{i-1}=y_{i-1}$ and $x_i \lt y_i$.

一个包含 $n$ 个数的序列被称为排列（permutation），当且仅当它恰好包含从 $1$ 到 $n$ 的所有整数各一次。例如，序列 $[3, 1, 4, 2]$、$[1]$ 和 $[2,1]$ 是排列，但 $[1,2,1]$、$[0,1]$ 和 $[1,3,4]$ 不是。

对于长度为偶数 $n$ 的排列 $p$，可构造一个长度为 $\frac{n}{2}$ 的数组 $b$，使得：

• $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$，使得能由该 $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$。

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one even integer $n$ ($2 \le n \le 2 \cdot 10^5$).

The second line of each test case contains exactly $\frac{n}{2}$ integers $b_i$ ($1 \le b_i \le n$) — elements of array $b$.

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

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来是各测试用例的描述。

每个测试用例的第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含恰好 $\frac{n}{2}$ 个整数 $b_i$（$1 \le b_i \le n$），即数组 $b$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, print on a separate line:

• lexicographically minimal permutation $p$ such that you can make an array $b$ from it;
• or a number -1 if the permutation you are looking for does not exist.

对于每个测试用例，在单独一行中输出：

• 字典序最小的排列 $p$，使得可以从它构造出数组 $b$；
• 或者如果所求的排列不存在，则输出数字 $-1$。

The first test case is parsed in the problem statement.

第一个测试用例已在题目描述中解析。