Restoring Permutation
Contest: Codeforces Round 623 (Div. 2, based on VK Cup 2019-2020 - Elimination Round, Engine)
Difficulty rating: 1200
Tags: greedy

You are given a sequence $$$b_1, b_2, \ldots, b_n$$$. Find the lexicographically minimal permutation $$$a_1, a_2, \ldots, a_{2n}$$$ such that $$$b_i = \min(a_{2i-1}, a_{2i})$$$, or determine that it is impossible.

Input format:
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$).

The first line of each test case consists of one integer $$$n$$$ — the number of elements in the sequence $$$b$$$ ($$$1 \le n \le 100$$$).

The second line of each test case consists of $$$n$$$ different integers $$$b_1, \ldots, b_n$$$ — elements of the sequence $$$b$$$ ($$$1 \le b_i \le 2n$$$).

It is guaranteed that the sum of $$$n$$$ by all test cases doesn't exceed $$$100$$$.

Output format:
For each test case, if there is no appropriate permutation, print one number $$$-1$$$.

Otherwise, print $$$2n$$$ integers $$$a_1, \ldots, a_{2n}$$$ — required lexicographically minimal permutation of numbers from $$$1$$$ to $$$2n$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
5
1
1
2
4 1
3
4 1 3
4
2 3 4 5
5
1 5 7 2 8

Example output:
1 2 
-1
4 5 1 2 3 6 
-1
1 3 5 6 7 9 2 4 8 10

Editorial:
This problem has a greedy solution. As you know the $$$b_i$$$, which is equal to $$$\min(a_{2i-1}, a_{2i})$$$, then one of $$$a_{2i-1}, a_{2i}$$$ should be equal to $$$b_i$$$. Which one? Of course, $$$a_{2i-1}$$$, because we want to get the lexicographically minimal answer, and we want to place a smaller number before the larger number.
So, we know that $$$a_1 = b_1$$$, $$$a_3 = b_2$$$, $$$a_5 = b_3$$$, and so on, so we know all elements of the permutation with odd indices. What number should be placed at $$$a_2$$$? We know that $$$a_2 \ge a_1$$$ (as $$$a_1 \ne a_2$$$, and $$$b_1 = \min(a_1, a_2)$$$). So, let's take the $$$a_2 = x$$$ for minimal possible $$$x$$$ such that $$$x \ge a_1$$$ and $$$x \ne a_1, x \ne a_3, \ldots, x \ne a_{2n-1}$$$. If there is no such $$$x$$$ (if all numbers greater than $$$a_1$$$ are already used), there is no appropriate permutation. Otherwise, we should take $$$a_2=x$$$ and resume the process.
The question is, why do we can place the minimal not used integer each time? Suppose there is another optimal answer $$$a'_1, a'_2, \ldots, a'_{2n}$$$, and we get $$$a_1, a_2, \ldots, a_{2n}$$$ or we didn't get any permutation by our greedy algorithm. As these two sequences are different, there is the first $$$k$$$ such that $$$a'_{2k} \ne a_{2k}$$$. As we tried to take the minimal possible $$$a_{2k}$$$, there are two options:
• $$$a_{2k} > a'_{2k}$$$. This is impossible as we tried to take the minimal possible $$$a_{2k}$$$, contradiction;
• $$$a_{2k} < a'_{2k}$$$. As $$$a'$$$ is «optimal correct» answer, we didn't finish our sequence $$$a$$$. Let's see, where is the number $$$a_{2k}$$$ in the sequence $$$a'$$$. It should be on some position $$$2l$$$, where $$$l>k$$$ (as $$$2k$$$ is the first difference between the sequences). But we can swap $$$a'_{2k}$$$ and $$$a'_{2l}$$$ and get smaller, but still correct sequence $$$a"$$$, so $$$a'$$$ is not optimal. Contradiction.