eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Странная сортировка

Странная сортировка

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Имеется последовательность из n целых чисел a[1], a[2], …, a[n]. Необходимо упорядочить ее элементы таким образом, чтобы никакие два последовательных числа не имели последовательных значений. Другими словами, в результирующей последовательности имеет место неравенство a[i] + 1a[i+1] (0 < i < n).

Если существует несколько последовательностей, удовлетворяющих условию, то вывести лексикографически наименьшую.

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

Состоит из нескольких тестов. Первая строка каждого теста содержит длину последовательности n (1n50000). Вторая строка содержит n целых чисел a[1], a[2], ..., a[n], разделенных одним пробелом. Каждое число по модулю не превосходит 10^9. Последний тест содержит n = 0 и не обрабатывается.

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

Для каждого теста в отдельной строке вывести результирующую последовательность. Числа выходной последовательности разделять одним пробелом. Вывести "No solution" (без кавычек), если требуемой последовательности не существует.

Пример

Входные данные #1
2
1 2 
0
Выходные данные #1
2 1
Источник All-Ukrainian Collegiate Programming Contest Semi-Final 2010