Ледi та перестановка Козака Вуса
Козак Вус має стратегiчно важливу перестановку a розмiру 2 · n − 1. Вiн шифрує перестановкумасивом b, де b[i] — це медiана† пiдмасиву a[1], a[2], . . . , a[2·i−1]. Ледi перехопила шифровку i просить вас знайти будь-яку вiдповiдну перестановку.
Вхідні дані
Перший рядок мiстить одне цiле число n (1 ≤ n ≤ 100 000) — розмiр шифровки.
Другий рядок мiстить n цiлих чисел b[1], b[2], . . . , b[n] (1 ≤ b[i] ≤ 2·n−1) — медiани.
Гарантується, що вхiднi тести такi, що вiдповiдь завжди iснує.
Вихідні дані
В єдиному рядку виведiть 2 · n − 1 цiлих чисел a[1], a[2], . . . , a[2·i−1]. Якщо є декiлька варiантiв вiдповiдi, виведiть будь-який.
####ПримiткаУ першому прикладi:
• b[1] = 1 — медiана масиву (1)
• b[2] = 3 — медiана масиву (1, 3, 9)
• b[3] = 3 — медiана масиву (1, 3, 9, 2, 8)
• b[4] = 4 — медiана масиву (1, 3, 9, 2, 8, 4, 7)
• b[5] = 5 — медiана масиву (1, 3, 9, 2, 8, 4, 7, 5, 6)
.Перестановкою довжини k називається послiдовнiсть цiлих чисел вiд 1 до k, де кожне число зустрiчається рiвно один раз.
Медiаною масиву непарної довжини називається елемент, який при сортуваннi масиву знаходиться по середині.