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

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

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

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

Входные данные

Первая строка содержит целое число $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)$ — элементы массива.

Выходные данные

Если упорядочить массив Вуса невозможно, выведите единственное число $-1$.

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

Примеры

Примечание

В первом примере существует единственное упорядочение.

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

В третьем примере правильного упорядочения не существует (в массиве всегда будут две единицы на соседних позициях).

Оценивание

В этой задаче используется потестовая оценка. Некоторые дополнительные ограничения:

• ($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$