题目描述

一个包含从 $1$ 到 $n$ 的所有数字且仅出现一次的序列被称为排列。例如，序列 $[3,1,4,2]$、$[1]$ 和 $[2,1]$ 是排列，但 $[1,2,1]$、$[0,1]$ 和 $[1,3,4]$ 不是。

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

• $b_i=max(p_{2i−1},p_{2i})$

其中 $1≤i≤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,…,x_n$ 在字典序上小于排列 $y_1,y_2,…,y_n$ 当且仅当存在 $i(1≤i≤n)$ 使得 $x_1=y_1,x_2=y_2,…,x_{i−1}=y_{i−1}$ 且 $x_i<y_i$。

输入格式

第一行一个整数 $t (1≤t≤10^4)$，表示数据组数。

对于每组数据：

第一行一个偶数 $n(2≤n≤2⋅10^5)$，表示排列 $p$ 的长度。

第二行 $\frac n2$ 个整数 $b_i (1≤b_i≤n)$ ，表示数组 $b$ 的元素。

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

输出格式

对于每组数据，请在单独的一行上输出：

• 字典序最小的排列 $p$，使得可以通过 $p$ 构造出数组 $b$。
• 或者输出 -1，表示不存在满足条件的排列 $p$。

测试样例

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

样例说明

第一个测试用例已经在问题陈述中给出。