如果 $$$n$$$ 数字序列包含从 $$$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})$$$ for $$$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$$$,找到按字典顺序排列的最小排列 $$$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$$$)。
每个测试用例的第二行恰好包含 $$$\frac{n}{2}$$$ 整数 $$$b_i$$$ ($$$1 \le b_i \le n$$$) — 数组 $$$b$$$ 的元素。
保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上打印:
- 按字典顺序最小排列 $$$p$$$,这样你就可以从中创建一个数组 $$$b$$$;
- 如果您要查找的排列不存在,则为数字 -1。
示例
输入 #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
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
注意
第一个测试用例在问题陈述中解析。