Задача №114099. День рождения
У ковбоя Влада день рождения! На праздник собрались \(n\) детей. Чтобы поздравить ковбоя, дети решили водить вокруг Влада хоровод. Среди детей, пришедших к Владу, есть и высокие, и низкие, поэтому если они встанут в хороводе как угодно, многим из них может быть неудобно, потому что если в хороводе рядом стоят очень высокий и очень низкий ребёнок, им трудно держаться за руки. Поэтому дети решили встать в хоровод так, чтобы максимальная разность ростов двух соседних детей была минимальной.
Более формально, пусть \(n\) детей выстроились в хоровод. Пронумеруем их целыми числами от \(1\) до \(n\) так, чтобы справа от ребёнка с номером \(i\) стоял ребёнок с номером \(i + 1\), а справа от ребёнка с номером \(n\) стоял ребёнок с номером \(1\). Тогда неудобством этого хоровода назовём максимальную разность между ростом детей, которые стоят рядом. Обратите внимание, что разностью в росте двух детей называется разность между ростом более высокого и более низкого ребёнка, таким образом, разность в росте двух детей всегда неотрицательна.
Помогите детям и определите, в каком порядке им надо выстроиться в круг, чтобы минимизировать неудобство получившегося хоровода. Обратите внимание, что все \(n\) детей должны оказаться в хороводе.
В первой строке содержится одно целое число \(n\) (\(2 \leq n \leq 10^5\)) — количество детей, которые пришли на день рождения ковбоя Влада.
Во второй строке заданы \(n\) целых чисел \(a_i\) (\(1 \leq a_i \leq 10^9\)) — рост каждого из детей. Рост детей задан в нанометрах и уменьшен на \(10^9\), таким образом, рост ребёнка с \(a_i = 1\) чуть выше метра, а рост ребёнка с \(a_i = 10^9\) составляет два метра.
Выведите \(n\) целых чисел — значения роста детей в порядке, в котором они должны встать в хоровод. В этом порядке соседними будут дети с номерами \(i\) и \(i + 1\), а также дети с номерами \(1\) и \(n\). Если оптимальных хороводов несколько, то выведите любой из них.
В первом примере неудобство хоровода равно \(1\), так как разность в росте между соседними детьми равна \(1\), \(1\), \(1\), \(1\) и \(0\) соответственно.
Обратите внимание, что последовательности \([2, 3, 2, 1, 1]\), \([3, 2, 1, 1, 2]\) задают те же хороводы и отличаются только выбором ребёнка с номером \(1\).
Во втором примере неудобство хоровода равно \(20\), так как разность в росте детей высотой \(10\) и \(30\) равна \(20\).
В данной задаче \(25\) тестов, помимо тестов из условия. Каждый из них оценивается в \(4\) балла. Результаты работы ваших решений на первых \(15\) тестах будут доступны во время соревнования. Результаты работы на остальных \(10\) будут доступны после окончания соревнования.
Решения, корректно работающие при \(1 \leq n \leq 5\), наберут не менее \(20\) баллов.
Решения, корректно работающие при \(a_i = i\), наберут не менее \(40\) баллов.
5 2 1 1 3 2
1 2 3 2 1
3 30 10 20
10 30 20