Леди и перестановка Казака Уса

Казак Вус обладает стратегически важной перестановкой ( a ) длиной ( 2 \cdot n - 1 ). Он зашифровывает эту перестановку с помощью массива ( b ), где ( b[i] ) — это медиана† подмассива ( a[1], a[2], \ldots, a[2 \cdot i - 1] ). Леди перехватила шифровку и просит вас восстановить любую соответствующую перестановку.

Формат входных данных

Первая строка содержит одно целое число ( n ) ((1 \leq n \leq 100,000)) — размер шифровки.

Вторая строка содержит ( n ) целых чисел ( b[1], b[2], \ldots, b[n] ) ((1 \leq b[i] \leq 2 \cdot n - 1)) — медианы.

Гарантируется, что входные данные таковы, что решение всегда существует.

Формат выходных данных

Выведите в одной строке ( 2 \cdot n - 1 ) целых чисел ( a[1], a[2], \ldots, a[2 \cdot n - 1] ). Если существует несколько решений, вы можете вывести любое из них.

Примеры

Примечание

В первом примере:

• ( b[1] = 1 ) — медиана массива ( (1) )

• ( b[2] = 3 ) — медиана массива ( (1, 3, 9) )

• ( b[3] = 3 ) — медиана массива ( (1, 3, 9, 2, 8) )

• ( b[4] = 4 ) — медиана массива ( (1, 3, 9, 2, 8, 4, 7) )

• ( b[5] = 5 ) — медиана массива ( (1, 3, 9, 2, 8, 4, 7, 5, 6) )

Перестановкой длины ( k ) называется последовательность целых чисел от 1 до ( k ), где каждое число встречается ровно один раз.

Медианой массива нечетной длины называется элемент, который при сортировке массива находится посередине.