codeforces#P1759G. Restore the Permutation

    ID: 33383 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>binary searchdata structuresgreedymath*1900

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