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