У ковбоя Влада день рождения! На праздник собрались \(n\) детей. Чтобы поздравить Влада, дети решили водить вокруг него хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, то рядом могут оказаться очень высокий и очень низкий ребёнок, и им будет трудно держаться за руки. Поэтому дети хотят встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была бы минимальной возможной.
Формально, пронумеруем детей от \(1\) до \(n\) по кругу, то есть для каждого \(i\) ребёнок с номером \(i\) является соседним с рёбенком с номером \(i+1\), а также ребёнок с номером \(1\), является соседом с ребёнок с номером \(n\). Тогда неудобством этого хоровода назовём максимальный модуль разности ростов детей, которые стоят рядом.
Помогите детям определить в каком порядке им надо перестроиться, чтобы минимизировать неудобство получившегося хоровода.
Выходные данные
Выведите \(n\) целых чисел — роста детей в порядке, в котором они должны встать в хоровод. Вы можете начинать вывод с любого из детей в круге.
В случае, если существует несколько возможных ответов — выведите любой из них.
Примечание
В первом примере неудобство хоровода равно \(1\), так как разности ростов между соседними детьми равны \(1\), \(1\), \(1\) и \(0\). Обратите внимание, что последовательности \([2, 3, 2, 1, 1]\), \([3, 2, 1, 1, 2]\) задают те же хороводы и отличаются лишь началом отсчёта.
Во втором примере неудобство хоровода равно \(20\), так как разность ростов детей с ростами \(10\) и \(30\) равна \(20\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 1 1 3 2
|
1 2 3 2 1
|
|
2
|
3
30 10 20
|
10 20 30
|