Дивне сортування
Дивне сортування
Дано послідовність з n цілих чисел a1
, a2
, ..., an
. Впорядкувати її елементи таким чином, щоб жодні два послідовних числа не мали послідовних значень. Іншими словами, в результуючій послідовності має місце нерівність ai
+ 1 ≠ ai+1
(0 < i < n).
Якщо існує декілька послідовностей, що задовольняють умову, то вивести лексикографічно найменшу.
Вхідні дані
Містить декілька тестів. Первший рядок кожного тесту містить довжину послідовності n (1 ≤ n ≤ 50000). Другий рядок містить n цілих чисел a1
, a2
, …, an
, відокремлених одним пропуском. Кожне число по модулю не перевищує 109
. Останній тест містить n = 0 і не опрацьовується.
Вихідні дані
Для кожного тесту в окремому рядку вивести результуючу послідовність. Числа вихідної послідовності повині відокремлюватись одним пропуском. Вивести "**No solution**" (без лапок) якщо потрібної послідовності не існує.
2 1 2 0
2 1