Constructing a Permutation from Prefix Medians

Given a positive integer $N$ and a sequence $B=[B_1,B_2,\dots,B_N]$, where $B$ is defined as the prefix medians of a permutation $A$ of the numbers $1,2,\dots,2N-1$, your task is to construct one such permutation $A$. In other words, let $A$ be a permutation of $\{1,2,\dots,2N-1\}$ and define its prefix-median sequence $B$ of length $N$ by letting [ B_i = \text{median}(A_1,A_2,\dots,A_{2i-1}), \quad 1\le i\le N. ] Here the median of an odd-length sequence is the element in the middle when the sequence is sorted in non‑decreasing order. It is known that in any permutation of $\{1,2,\dots,2N-1\}$ the median of the whole sequence is always $N$. Thus a necessary condition for the input is $B_N=N$, and one may show that if a solution exists then the input $B$ has special properties. You are guaranteed that the given $B$ is valid (i.e. there exists at least one permutation $A$ having $B$ as its prefix medians).

One observation is that the elements at odd positions in $A$ must be exactly $B_1, B_2, \dots, B_N$ (in that order) because the $i$-th prefix, which has length $2i-1$, must have $B_i$ as its median. The remaining $N-1$ positions (the even indices) must be filled with the numbers from the set [ S = {1,2,\dots,2N-1} \setminus {B_1,B_2,\dots,B_N}, ] in some order so that for every $2\le i\le N$ the following condition holds. Let $X_1,X_2,\dots,X_{N-1}$ be the numbers placed at positions $2,4,\dots,2N-2$. Then for every $2\le i\le N$, in the prefix [ [A_1, A_2, \dots, A_{2i-1}] = [B_1, X_1, B_2, X_2, \dots, B_{i-1}, X_{i-1}, B_i], ] it must be that exactly $i-1$ numbers are strictly less than $B_i$. That is, [ #{j:1\le j\le i-1,; B_j < B_i} + #{j:1\le j\le i-1,; X_j < B_i} = i-1. ] Your task is to choose a permutation of $S$ for the even positions (the $X_j$’s) so that all these conditions are met, and then output the full permutation $A$.

It is guaranteed that the input $B$ is valid; if there are multiple answers, any one is acceptable.

inputFormat

The first line contains a single integer $N$ ($1\le N\le 10$).
The second line contains $N$ space‐separated integers, $B_1, B_2, \dots, B_N$.

Note: It is guaranteed that $B_N=N$, and that there exists at least one permutation $A$ of $\{1,2,\dots,2N-1\}$ whose prefix medians are exactly $B$.

outputFormat

Output $2N-1$ space-separated integers --- a permutation $A$ of $\{1,2,\dots,2N-1\}$ whose prefix medians are exactly $B$.

sample

2
3 2

3 1 2