Problem Description

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

Input Format

The first line contains an integer $N$.

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

Output Format

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.

5
1 3 3 4 5

1 9 3 2 4 8 7 5 6

Hint

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 Day 1 T3 medians.

Thanks to

Translated by ChatGPT 5