Let ~A~ be a permutation of ~1, 2, \dots, 2N-1~.
We define the prefix medians of ~A~ as an array ~B~ with ~N~ elements: where ~B[i]~ is the median of ~A[1], A[2], \dots, A[2i-1]~.
Note: The median of a list of ~M~ numbers (where ~M~ is odd) can be found by sorting the numbers and picking the middle one.

Task

You are given ~N~ and the array ~B~. You are asked to determine a permutation ~A~ whose prefix medians are precisely ~B~.

Input Specification

The input contains 2 lines. The first line contains one integer, ~N~. The second line describes ~B~: ~N~ integers, separated by space.

Output Specification

The output should contain ~A~: one line with ~2N-1~ integers separated by space. If there are multiple permutations ~A~ leading to the same input array ~B~, you may output any one. In all test data, there will always be at least one solution.

Constraints

• ~1 \le A[i] \le 2N-1~, for every ~i~ from ~1~ to ~2N-1~
• ~1 \le B[i] \le 2N-1~, for every ~i~ from ~1~ to ~N~
• ~1 \le N \le 100\,000~
• ~60\%~ of the tests will have ~N \le 1\,000~

Sample Input

5
1 3 3 4 5

Sample Output

1 9 3 2 4 8 7 5 6