Prefix Medians

Time limit1sMemory limit128 MB

Summary

Given the prefix medians B of an unknown permutation of 1 to 2N-1, reconstruct the lexicographically smallest permutation that produces exactly those medians.

Level: Hard8 of 10
Topics: Greedy, Implementation, Sorting, Brute force
Solved: No attempts yet

Problem

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

Input

The first line contains one integer $N$ .

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

Output

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.

Constraints

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

Examples5

Example 1
Input
```
5
1 3 3 4 5
```
Expected output
```
1 3 4 2 5 6 7 8 9
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
4
1 2 3 4
```
Expected output
```
1 2 3 4 5 6 7
```
Example 4
Input
```
2
3 2
```
Expected output
```
3 1 2
```
Example 5
Input
```
3
5 3 3
```
Expected output
```
5 1 3 2 4
```