Задачи
Козак Вус та лексикографія
Козак Вус та лексикографія
Нещодавно Козаку подарували масив $a$ з $n$ цілих чисел.
Вус одразу захотів впорядкувати елементи масиву таким чином, щоб будь-які сусідні числа в масиві були різні. Серед усіх таких впорядкувань він хоче знайти лексикографічно найменше.
Нагадаємо, що лексикографічний порядок задається наступним чином. Нехай маємо два масиви. Знайдемо першу позицію, у якій елементи двох масивів відрізняються. Тоді якщо на цій позиції елемент першого масиву менший за елемент другого, то перший масив лексикографічно менший за другий, інакше "--- навпаки, перший масив більший за другий. Наприклад, виконуються наступні нерівності: $[10, 3, 1]$ < $[10, 4, 5]$, $[1, 1, 1] < [1, 2, 3], [1, 2, 3] < [10, 10, 10]$.
\InputFile
Перший рядок містить ціле число $n$ $(1 \leq n \leq 5 \cdot 10^5)$ "--- кількість елементів масиву.
Другий рядок містить $n$ цілих чисел $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 5 \cdot 10^5)$ "--- елементи масиву.
\OutputFile
Якщо впорядкувати масив Вуса неможливо виведіть єдине число $-1$.
Інакше виведіть $n$ цілих чисел "--- лексикографічно мінімальне впорядкування масива Вуса.
\Note
У першому прикладі існує єдине впорядкування.
У другому прикладі існують й інші впорядкування, наприклад: $[1, 2, 3, 4, 1, 2]$ або $[1, 4, 1, 2, 3, 2]$. Але всі такі впорядкування лексикографічно більші за $[1, 2, 1, 2, 3, 4]$.
У третьому прикладі правильного впорядкування не існує (в масиві завжди будуть дві одинички на сусідніх позиціях).
\Scoring
У цій задачі використовується \textbf{потестове} оцінювання. Деякі додаткові обмеження:
\begin{itemize}
\item ($5$ балів): $n \leq 10^3, a_i \leq 2$
\item ($10$ балів): $n \leq 10^3, a_i \leq 3$
\item ($25$ балів): $n \leq 10^3, a_i \leq 5 \cdot 10^5$
\item ($5$ балів): $n \leq 5 \cdot 10^5, a_i \leq 2$
\item ($10$ балів): $n \leq 5 \cdot 10^5, a_i \leq 3$
\item ($45$ балів): $n \leq 5 \cdot 10^5, a_i \leq 5 \cdot 10^5$
\end{itemize}
Входные данные #1
5 3 1 2 3 3
Выходные данные #1
3 1 3 2 3
Входные данные #2
6 2 3 1 1 2 4
Выходные данные #2
1 2 1 2 3 4
Входные данные #3
4 1 2 1 1
Выходные данные #3
-1