Козак Вус має стратегiчно важливу перестановку a розмiру 2 · n − 1. Вiн шифрує перестановку масивом b, де bi — це медiана† пiдмасиву a1, a2, . . . , a2·i−1. Ледi перехопила шифровку i просить вас знайти будь-яку вiдповiдну перестановку.

Формат вхiдних даних

Перший рядок мiстить одне цiле число n (**1 ≤ n ≤ 100 000**) — розмiр шифровки.

Другий рядок мiстить n цiлих чисел b1, b2, . . . , bn (**1 ≤ bi ≤ 2·n−1**) — медiани.

Гарантується, що вхiднi тести такi, що вiдповiдь завжди iснує.

Формат вихiдних даних

В єдиному рядку виведiть 2 · n − 1 цiлих чисел a1, a2, . . . , a2·i−1. Якщо є декiлька варiантiв вiдповiдi, виведiть будь-який.

Примiтка

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

• b1 = 1 — медiана масиву (1)

• b2 = 3 — медiана масиву (1, 3, 9)

• b3 = 3 — медiана масиву (1, 3, 9, 2, 8)

• b4 = 4 — медiана масиву (1, 3, 9, 2, 8, 4, 7)

• b5 = 5 — медiана масиву (1, 3, 9, 2, 8, 4, 7, 5, 6)

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

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