Let ~A~ be a permutation of ~1, 2, 3 \ldots, 2N - 1~.
We define the prefix medians of ~A~ as an array ~B~ with ~N~ elements: where ~\mathrm B[i]~ is the median of ~\mathrm A, \mathrm A, \ldots, \mathrm 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.
You are given ~N~ and the array ~B~. You are asked to determine a permutation A whose prefix medians are precisely B.
The input contains 2 lines. The first line contains one integer, ~N~. The second line describes ~B~: ~N~ integers, separated by space.
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.
- ~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~
5 1 3 3 4 5
1 9 3 2 4 8 7 5 6