Козак Вус та лексикографія

Нещодавно Козаку подарували масив $a$ з $n$ цілих чисел.

Вус одразу захотів впорядкувати елементи масиву таким чином, щоб будь-які сусідні числа в масиві були різні. Серед усіх таких впорядкувань він хоче знайти лексикографічно найменше.

Нагадаємо, що лексикографічний порядок задається наступним чином. Нехай маємо два масиви. Знайдемо першу позицію, у якій елементи двох масивів відрізняються. Тоді якщо на цій позиції елемент першого масиву менший за елемент другого, то перший масив лексикографічно менший за другий, інакше — навпаки, перший масив більший за другий. Наприклад, виконуються наступні нерівності: $[10,3,1]$ < $[10,4,5]$, $[1,1,1]<[1,2,3],[1,2,3]<[10,10,10]$.

Input

Перший рядок містить ціле число $n$ $(1\le n\le 5\cdot 10^5)$ — кількість елементів масиву.

Другий рядок містить $n$ цілих чисел $a_1,a_2,...,a_n$ $(1\le a_i\le 5\cdot 10^5)$ — елементи масиву.

Output

Якщо впорядкувати масив Вуса неможливо виведіть єдине число $-1$.

Інакше виведіть $n$ цілих чисел — лексикографічно мінімальне впорядкування масива Вуса.

Examples

Note

У першому прикладі існує єдине впорядкування.

У другому прикладі існують й інші впорядкування, наприклад: $[1,2,3,4,1,2]$ або $[1,4,1,2,3,2]$. Але всі такі впорядкування лексикографічно більші за $[1,2,1,2,3,4]$.

У третьому прикладі правильного впорядкування не існує (в масиві завжди будуть дві одинички на сусідніх позиціях).

Scoring

У цій задачі використовується потестове оцінювання. Деякі додаткові обмеження:

• ($5$ балів): $n\le 10^3,a_i\le 2$

• ($10$ балів): $n\le 10^3,a_i\le 3$

• ($25$ балів): $n\le 10^3,a_i\le 5\cdot 10^5$

• ($5$ балів): $n\le 5\cdot 10^5,a_i\le 2$

• ($10$ балів): $n\le 5\cdot 10^5,a_i\le 3$

• ($45$ балів): $n\le 5\cdot 10^5,a_i\le 5\cdot 10^5$