Леді та перестановка Козака Вуса

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 100000$ 1 \le n \le 100\,000) — розмір шифрування.

Другий рядок містить $n$ цілих чисел $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n ( $1 \leq b_{i} \leq 2 n - 1$ 1 \le b_i \le 2n-1) — медіани відповідних підмасивів.

Гарантується, що для заданого входу відповідь завжди існує.

Вихідні дані

Виведіть в одному рядку $2 n - 1$ 2n - 1 цілих чисел $a_{1}, a_{2}, \dots, a_{2 n - 1}$ a_1, a_2, \ldots, a_{2n-1}. Якщо існує кілька правильних відповідей, виведіть будь-яку з них.

Приклади

Приклад 1

Loading

Приклад 2

Loading

Примітка

У першому прикладі:

$b_{1} = 1$ b_1 = 1 — медіана масиву $(1)$
$b_{2} = 3$ b_2 = 3 — медіана масиву $(1, 3, 9)$ (1, 3, 9)
$b_{3} = 3$ b_3 = 3 — медіана масиву $(1, 3, 9, 2, 8)$ (1, 3, 9, 2, 8)
$b_{4} = 4$ b_4 = 4 — медіана масиву $(1, 3, 9, 2, 8, 4, 7)$ (1, 3, 9, 2, 8, 4, 7)
$b_{5} = 5$ b_5 = 5 — медіана масиву $(1, 3, 9, 2, 8, 4, 7, 5, 6)$ (1, 3, 9, 2, 8, 4, 7, 5, 6)

Перестановка довжини $k$ — це послідовність цілих чисел від $1$ до $k$ , кожне з яких зустрічається рівно один раз.

Медіаною масиву непарної довжини називається елемент, який при сортуванні масиву знаходиться посередині.