Restore the Permutation

题意翻译

给定 $b_1\sim b_\frac n2$，求一个字典序最小的排列 $p_1\sim p_n$ 使得 $\forall i\in[1,\frac n2] \text{ s.t. }b_i = \max(p_{2i-1},p_{2i})$。 保证 $n$ 是偶数，且 $\sum n\leqslant 2\times10^5$。

题目描述

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.

输入输出样例

输入样例 #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

说明

The first test case is parsed in the problem statement.

**题目大意：**

给定一个长度为 $ \frac{n}{2} $ 的数组 $ b $，要求找到一个字典序最小的排列 $ p $ 使得 $ \forall i\in[1,\frac n2] $，都有 $ b_i = \max(p_{2i-1},p_{2i}) $。其中 $ n $ 是偶数，且所有测试用例中 $ n $ 的总和不超过 $ 2\times10^5 $。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数 $ 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 $ 的元素。

**输出格式：**
- 对于每个测试用例，输出一行结果：
- 如果存在满足条件的排列 $ p $，则输出这个排列。
- 如果不存在这样的排列，则输出 -1。**题目大意：** 给定一个长度为 $ \frac{n}{2} $ 的数组 $ b $，要求找到一个字典序最小的排列 $ p $ 使得 $ \forall i\in[1,\frac n2] $，都有 $ b_i = \max(p_{2i-1},p_{2i}) $。其中 $ n $ 是偶数，且所有测试用例中 $ n $ 的总和不超过 $ 2\times10^5 $。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $ 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 $ 的元素。 **输出格式：** - 对于每个测试用例，输出一行结果： - 如果存在满足条件的排列 $ p $，则输出这个排列。 - 如果不存在这样的排列，则输出 -1。