Кевину на день рождения подарили множество попарно различных чисел \(1, 2, 3, \ldots, n\).
Он хочет упорядочить эти числа таким образом, чтобы минимальное значение модуля разности двух соседних чисел было как можно больше. Более формально, если Кевин расположит числа в порядке \(p_1, p_2, \ldots, p_n\), он хочет максимизировать величину \(\)\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert,\(\) где \(|x|\) обозначает модуль числа \(x\).
Помогите Кевину сделать это.
Выходные данные
Для каждого набора входных данных выведите строку, содержащую \(n\) различных целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)), описывающую порядок чисел, при котором минимальное значение модуля разности двух соседних чисел максимально.
Формально, нужно вывести перестановку \(p\), которая максимизирует величину \(\min \limits_{i=1}^{n - 1} \lvert p_{i + 1} - p_i \rvert\).
Если существует несколько оптимальных решений, выведите любое из них.
Примечание
В первом наборе входных данных минимальное значение модуля разности двух соседних чисел равно \(\min \{\lvert 4 - 2 \rvert, \lvert 1 - 4 \rvert, \lvert 3 - 1 \rvert \} = \min \{2, 3, 2\} = 2\). Несложно показать, что это оптимальный ответ.
Во втором наборе входных данных любая перестановка чисел \(1, 2, 3\) является оптимальным ответом. Минимальное значение модуля разности двух соседних чисел равно \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
3
|
2 4 1 3
1 2 3
|