← 返回题目列表

Codeforces · 1759/G

G. 恢复排列

中文机器翻译题面 查看原题

如果 $$$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

注意

第一个测试用例在问题陈述中解析。