Козак Вус та лексикографія
Нещодавно Козаку подарували масив з цілих чисел.
Вус одразу захотів впорядкувати елементи масиву таким чином, щоб будь-які сусідні числа в масиві були різні. Серед усіх таких впорядкувань він хоче знайти лексикографічно найменше.
Нагадаємо, що лексикографічний порядок задається наступним чином. Нехай маємо два масиви. Знайдемо першу позицію, у якій елементи двох масивів відрізняються. Тоді якщо на цій позиції елемент першого масиву менший за елемент другого, то перший масив лексикографічно менший за другий, інакше "— навпаки, перший масив більший за другий. Наприклад, виконуються наступні нерівності: < , .
Вхідні дані
Перший рядок містить ціле число "— кількість елементів масиву.
Другий рядок містить цілих чисел "— елементи масиву.
Вихідні дані
Якщо впорядкувати масив Вуса неможливо виведіть єдине число .
Інакше виведіть цілих чисел "— лексикографічно мінімальне впорядкування масива Вуса.
Приклади
Примітка
У першому прикладі існує єдине впорядкування.
У другому прикладі існують й інші впорядкування, наприклад: або . Але всі такі впорядкування лексикографічно більші за .
У третьому прикладі правильного впорядкування не існує (в масиві завжди будуть дві одинички на сусідніх позиціях).
Оцінювання
У цій задачі використовується потестове оцінювання. Деякі додаткові обмеження:
( балів):
( балів):
( балів):
( балів):
( балів):
( балів):