Restore the Permutation
Description
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$
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<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$.
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.
Input
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$.
Output
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.
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
Note
The first test case is parsed in the problem statement.