Странная сортировка
Странная сортировка
Имеется последовательность из n целых чисел a[1]
, a[2]
, …, a[n]
. Необходимо упорядочить ее элементы таким образом, чтобы никакие два последовательных числа не имели последовательных значений. Другими словами, в результирующей последовательности имеет место неравенство a[i]
+ 1 ≠ a[i+1]
(0 < i < n).
Если существует несколько последовательностей, удовлетворяющих условию, то вывести лексикографически наименьшую.
Giriş verilənləri
Состоит из нескольких тестов. Первая строка каждого теста содержит длину последовательности n (1 ≤ n ≤ 50000). Вторая строка содержит n целых чисел a[1]
, a[2]
, ..., a[n]
, разделенных одним пробелом. Каждое число по модулю не превосходит 10^9
. Последний тест содержит n = 0 и не обрабатывается.
Çıxış verilənləri
Для каждого теста в отдельной строке вывести результирующую последовательность. Числа выходной последовательности разделять одним пробелом. Вывести "No solution" (без кавычек), если требуемой последовательности не существует.
Nümunə
2 1 2 0
2 1