Lady and the Permutation of Kozak Vus#9086
Cossack Vus possesses a strategically crucial permutation of length 2n - 1. He encrypts this permutation using an array , where each element b_i represents the median of the subarray a_1, a_2, \ldots, a_{2i-1}. The Lady intercepted this encryption and now seeks your help to determine any permutation that could correspond to this encryption.
The first line contains a single integer (1 \leq n \leq 100\ 000) — the size of the encryption.
The second line contains integers b_1, b_2, \ldots, b_n (1 \leq b_i \leq 2n-1) — the medians of the respective subarrays.
It is guaranteed that for the given input, a solution always exists.
Output 2n - 1 integers a_1, a_2, \ldots, a_{2n-1} in one line. If multiple valid permutations exist, you may output any of them.
Example 1
Example 2
In the first example:
b_1 = 1 — median of the array
b_2 = 3 — median of the array (1, 3, 9)
b_3 = 3 — median of the array (1, 3, 9, 2, 8)
b_4 = 4 — median of the array (1, 3, 9, 2, 8, 4, 7)
b_5 = 5 — median of the array (1, 3, 9, 2, 8, 4, 7, 5, 6)
A permutation of length is a sequence consisting of the integers from to , each occurring exactly once.
The median of an array of odd length is the element that is in the middle when the array is sorted.