e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Ukrainian Olympiad in Informatics, III Stage, II Round

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

Нещодавно Козаку подарували масив $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 секунда
Ліміт використання пам'яті 256 MiB
Вхідні дані #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
Автор Mark Grishechkin