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

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

1 секунда

256 мегабайтів

Середня

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

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

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

Вхідні дані

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

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

Вихідні дані

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

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

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

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

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

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

Оцінювання

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

( $5$ балів): $n \leq 1 0^{3}, a_{i} \leq 2$ n \leq 10^3, a_i \leq 2
( $10$ балів): $n \leq 1 0^{3}, a_{i} \leq 3$ n \leq 10^3, a_i \leq 3
( $25$ балів): $n \leq 1 0^{3}, a_{i} \leq 5 \cdot 1 0^{5}$ n \leq 10^3, a_i \leq 5 \cdot 10^5
( $5$ балів): $n \leq 5 \cdot 1 0^{5}, a_{i} \leq 2$ n \leq 5 \cdot 10^5, a_i \leq 2
( $10$ балів): $n \leq 5 \cdot 1 0^{5}, a_{i} \leq 3$ n \leq 5 \cdot 10^5, a_i \leq 3
( $45$ балів): $n \leq 5 \cdot 1 0^{5}, a_{i} \leq 5 \cdot 1 0^{5}$ n \leq 5 \cdot 10^5, a_i \leq 5 \cdot 10^5