eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 64 MiB

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

Input data

Перший рядок м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снує.

Output data

В єдиному рядку вивед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 масиву знаходиться по середині.

Examples

Input example #1
5
1 3 3 4 5
Output example #1
1 3 9 2 8 4 7 5 6 
Input example #2
4
1 2 3 4
Output example #2
1 2 7 3 6 4 5 
Source 2019-2020 ACM-ICPC, SEERC, 1/4 фiналу, Днiпро, Київ, Львiв, Миколаїв, Тернопiль, Харкiв, 14 вересня 2019