Уковбоя влада день рождения! на праздник собрались n детей. чтобы поздравить ковбоя, дети решили водить вокруг влада хоровод. среди детей, пришедших к владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, многим из них может быть неудобно, потому что если в хороводе
рядом стоят высокий и низкий ребёнок, им трудно держаться за руки. поэтому дети решили встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была минимальной. более формально, пусть n детей выстроились в хоровод. пронумеруем их целыми числами от 1 до n так, чтобы справа от
ребёнка с номером i стоял ребёнок с номером i + 1, а справа от ребёнка с номером n стоял ребёнок с номером 1. тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. обратите внимание, что разностью в росте двух детей называется разность между ростом
более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна. детям и определите, в каком порядке им надо выстроиться в круг, чтобы минимизи- ровать неудобство получившегося хоровода. обратите внимание, что все n детей должны оказаться в хороводе. формат
входных данных в первой строке содержится одно целое число n (2 ⩽ n ⩽ 105 ) — количество детей, которые пришли на день рождения ковбоя влада. во второй строке заданы n целых чисел ai (1 ⩽ ai ⩽ 109 ) — рост каждого из детей. рост детей задан в нанометрах и уменьшен на 109 , таким образом, рост
ребёнка с ai = 1 чуть выше метра, а рост ребёнка с ai = 109 составляет два метра. формат выходных данных выведите n целых чисел — значения роста детей в порядке, в котором они должны встать в хоровод. в этом порядке соседними будут дети с номерами i и i + 1, а также дети с номерами 1 и n. если
оптимальных хороводов несколько, то выведите любой из них. примеры стандартный ввод стандартный вывод 5 2 1 1 3 2 1 2 3 2 1 3 30 10 20 10 20 30