P6721 [BalkanOI 2011] medians

Let $A$ be any permutation of $1,2,3,\ldots,2\times N-1$. We define the prefix medians of $A$ as a sequence $B$ of length $N$, where $B_i$ is the median of $A_1,A_2,\ldots,A_{2\times i-1}$. You will be given the sequence $B$. Please construct a sequence $A$ such that its prefix medians are exactly $B$.

The first line contains an integer $N$. The next line contains $N$ integers, representing the sequence $B$.

Output one line with $2\times N-1$ integers, representing the sequence $A$ you construct. The testdata is guaranteed to have a solution; you only need to output any one valid solution.

#### Constraints - For $60\%$ of the testdata, it is guaranteed that $N\le 10^3$. - For $100\%$ of the testdata, it is guaranteed that $1\le N\le 10^5$, $1\le A_i,B_i\le 2\times N-1$, and the testdata is guaranteed to have a solution. #### Notes This problem is translated from [Balkan Olympiad in Informatics 2011](http://www.boi2011.ro/boi2011/) [Day 1](http://www.boi2011.ro/boi2011/?pagina=probleme) [T3 medians](http://www.boi2011.ro/resurse/tasks/medians.pdf). Thanks to @[using](https://www.luogu.com.cn/user/193198) for providing the SPJ. Translated by ChatGPT 5