Вы — дизайнер игр, и хотите создать полосу препятствий. Игрок будет идти слева направо. У вас уже есть \(n\) высот гор, и вы хотите расположить эти высоты так, чтобы абсолютная разность между высотами первой и последней гор была как можно меньше.
Кроме того, вы хотите сделать игру сложной, а поскольку идти в гору или по равнине сложнее, чем спускаться по склону, то сложность уровня будет равна количеству гор \(i\) (\(1 \leq i < n\)) таких, что \(h_i \leq h_{i+1}\), где \(h_i\) — высота \(i\)-й горы. Вы не хотите потратить впустую ни одну из смоделированных гор, поэтому должны использовать их все.
Из всех вариантов, минимизирующих \(|h_1-h_n|\), найдите самый сложный. Если существует несколько порядков, удовлетворяющих этим требованиям, вы можете найти любой.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел — заданные высоты в порядке, который максимизирует сложность уровня среди всех порядков, минимизирующих \(|h_1-h_n|\).
Если существует несколько порядков, удовлетворяющих этим требованиям, вы можете вывести любой.
Примечание
В первом наборе входных данных:
Игрок начинает с высоты \(2\), затем поднимается на высоту \(4\), увеличивая сложность на \(1\). После этого он спускается на высоту \(1\), и сложность не меняется, потому что он спускается вниз. Наконец, игрок поднимется на высоту \(2\), и сложность увеличится на \(1\). Абсолютная разность между начальной и конечной высотой равна \(0\), а следовательно минимальна. Трудность максимальна при данных условиях.
Во втором наборе входных данных:
Игрок начинает с высоты \(1\), затем поднимается до высоты \(3\), увеличивая сложность на \(1\). Абсолютная разниость между начальной и конечной высотой равна \(2\) и она минимально возможная, так как это единственные высоты. Трудность максимальна.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
4 2 1 2
2
3 1
|
2 4 1 2
1 3
|