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$.


-----Input-----

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$.


-----Output-----

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.


-----Examples-----

Input
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
Output
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


-----Note-----

The first test case is parsed in the problem statement.

Difficulty: HARD
Tags: Constructive algorithms

Sorting

Greedy algorithms

Mathematics

Data structures
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
from bisect import bisect_right as bs
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	st = set(b)
	if len(st) != n // 2:
		print(-1)
		continue
	res = [i for i in range(1, n + 1) if i not in st]
	ans = []
	for i in range(n // 2 - 1, -1, -1):
		j = bs(res, b[-1]) - 1
		if j == -1:
			ans = -1
			break
		ans.extend((b[-1], res[j]))
		del b[-1]
		del res[j]
	if isinstance(ans, int):
		print(ans)
	else:
		sys.stdout.write(' '.join(map(str, ans[::-1])) + '\n')


from bisect import bisect_right as bs
for _ in range(int(input())):
	n = int(input())
	b = input().split()
	ans = [0] * n
	used = [0] * (n + 1)
	for (i, x) in enumerate(b):
		q = int(x)
		ans[2 * i + 1] = q
		used[q] = 1
	res = [i for i in range(1, n + 1) if not used[i]]
	if len(res) != n / 2:
		print(-1)
		continue
	for i in range(n // 2 - 1, -1, -1):
		j = bs(res, ans[2 * i + 1]) - 1
		if j == -1:
			ans = -1
			break
		ans[2 * i] = res[j]
		del res[j]
	if isinstance(ans, int):
		print(ans)
	else:
		print(*ans)


from bisect import bisect_right as bs
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	st = set(b)
	if len(st) != n // 2:
		print(-1)
		continue
	res = [i for i in range(1, n + 1) if i not in st]
	ans = []
	for i in range(n // 2 - 1, -1, -1):
		j = bs(res, b[-1]) - 1
		if j == -1:
			ans = -1
			break
		ans.extend((b[-1], res[j]))
		del b[-1]
		del res[j]
	if isinstance(ans, int):
		print(ans)
	else:
		print(*ans[::-1])


from queue import PriorityQueue

def f(n: int):
	maxes = list(map(int, input().split()))
	pairs = [[] for _ in range(len(maxes))]
	used_numbers = {x: i for (i, x) in enumerate(maxes)}
	queue = PriorityQueue()
	for x in reversed(range(1, n + 1)):
		if x in used_numbers:
			i = used_numbers[x]
			pairs[i].append(x)
			if len(pairs[i]) == 1:
				queue.put(-i)
			continue
		if queue.empty():
			return [-1]
		i = -queue.get()
		pairs[i].append(x)
	result = []
	for (x, y) in pairs:
		result.extend((min(x, y), max(x, y)))
	return result
for _ in range(int(input())):
	print(' '.join(map(str, f(int(input())))))