Prefix Medians

Let $A$ be a permutation of $1, 2, 3, \ldots, 2N-1$.

Define the prefix medians of $A$ as an array $B$ with $N$ elements, where $B_i$ is the median of the first $2i-1$ elements $A_1, A_2, \ldots, A_{2i-1}$.

The median of a list of $M$ numbers, where $M$ is odd, is the middle value after the list is sorted.

You are given $N$ and the array $B$. Reconstruct a permutation $A$ whose prefix medians are exactly $B$.

The first line contains one integer $N$.

The second line contains $N$ integers $B_1, B_2, \ldots, B_N$ separated by spaces.

Print $A$ as a single line of $2N-1$ integers separated by spaces.

Several permutations may produce the same array $B$; among them, print the lexicographically smallest one. It is guaranteed that at least one valid permutation exists.

• $1 \le N \le 100,000$
• $1 \le B_i \le 2N-1$ for each $i$ ($1 \le i \le N$)
• A permutation $A$ with prefix medians $B$ is guaranteed to exist.