#GYM104777J. Complete the Permutation
Complete the Permutation
Description
You are given an incomplete permutation of length $2n - 1$, where only odd positions are filled in with odd numbers from $1$ to $2n-1$. Complete the permutation by filling in even positions with even numbers from $2$ to $2n-2$ so that no even number is a local extremum.
A permutation of length $k$ is an array of length $k$ which contains every integer from $1$ to $k$ (inclusive) exactly once. For example, $p=[4, 2, 6, 5, 3, 1]$ is a permutation of length $6$.
An element of a permutation is a local extremum if it is either greater than both its neighbours, or less than both its neighbours.
The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases.
The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of odd integers in the permutation.
The second line contains $n$ integers $p_1, p_3, p_5, \dots, p_{2n-1}$ ($1 \le a_i \le 2n-1$, all $p_i$ are odd and unique) — the elements on the odd positions of the permutation.
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
For each test case, print the answer on a separate line as follows:
- if the answer exists, print $n - 1$ integers $p_2, p_4, p_6, \dots, p_{2n-2}$ ($2 \le p_i \le 2n-2$). All these integers should be even and unique. In the permutation $[p_1, p_2, \dots, p_{2n-1}]$, no integer on an even position should be a local extremum. In case there are multiple answers, you may print any of them;
- otherwise, print one integer $-1$.
Input
The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases.
The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of odd integers in the permutation.
The second line contains $n$ integers $p_1, p_3, p_5, \dots, p_{2n-1}$ ($1 \le a_i \le 2n-1$, all $p_i$ are odd and unique) — the elements on the odd positions of the permutation.
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
Output
For each test case, print the answer on a separate line as follows:
- if the answer exists, print $n - 1$ integers $p_2, p_4, p_6, \dots, p_{2n-2}$ ($2 \le p_i \le 2n-2$). All these integers should be even and unique. In the permutation $[p_1, p_2, \dots, p_{2n-1}]$, no integer on an even position should be a local extremum. In case there are multiple answers, you may print any of them;
- otherwise, print one integer $-1$.
3
3
1 3 5
8
13 15 9 5 7 1 3 11
5
1 5 3 9 7
2 4
14 12 8 6 4 2 10
2 4 6 8
Note
In the first test case of the example, you are given an incomplete permutation $[1, \_, 3, \_, 5]$, where underscores denote missing even numbers. The sample output provides the only valid solution for that test case: $[1, 2, 3, 4, 5]$.
The only other way to insert even numbers into the given incomplete permutation is $[1, 4, 3, 2, 5]$, and that violates the extremum requirement, as here $4$ is greater than both its neighbours $1$ and $3$.