C. Сложные скалы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы — дизайнер игр, и хотите создать полосу препятствий. Игрок будет идти слева направо. У вас уже есть $$$n$$$ высот гор, и вы хотите расположить эти высоты так, чтобы абсолютная разность между высотами первой и последней гор была как можно меньше.

Кроме того, вы хотите сделать игру сложной, а поскольку идти в гору или по равнине сложнее, чем спускаться по склону, то сложность уровня будет равна количеству гор $$$i$$$ ($$$1 \leq i < n$$$) таких, что $$$h_i \leq h_{i+1}$$$, где $$$h_i$$$ — высота $$$i$$$-й горы. Вы не хотите потратить впустую ни одну из смоделированных гор, поэтому должны использовать их все.

Из всех вариантов, минимизирующих $$$|h_1-h_n|$$$, найдите самый сложный. Если существует несколько порядков, удовлетворяющих этим требованиям, вы можете найти любой.

Входные данные

Первая строка будет содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Затем следуют $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — количество гор.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$h_1,\ldots,h_n$$$ ($$$1 \leq h_i \leq 10^9$$$), где $$$h_i$$$ — высота $$$i$$$-й горы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — заданные высоты в порядке, который максимизирует сложность уровня среди всех порядков, минимизирующих $$$|h_1-h_n|$$$.

Если существует несколько порядков, удовлетворяющих этим требованиям, вы можете вывести любой.

Пример
Входные данные
2
4
4 2 1 2
2
3 1
Выходные данные
2 4 1 2 
1 3
Примечание

В первом наборе входных данных:

Игрок начинает с высоты $$$2$$$, затем поднимается на высоту $$$4$$$, увеличивая сложность на $$$1$$$. После этого он спускается на высоту $$$1$$$, и сложность не меняется, потому что он спускается вниз. Наконец, игрок поднимется на высоту $$$2$$$, и сложность увеличится на $$$1$$$. Абсолютная разность между начальной и конечной высотой равна $$$0$$$, а следовательно минимальна. Трудность максимальна при данных условиях.

Во втором наборе входных данных:

Игрок начинает с высоты $$$1$$$, затем поднимается до высоты $$$3$$$, увеличивая сложность на $$$1$$$. Абсолютная разниость между начальной и конечной высотой равна $$$2$$$ и она минимально возможная, так как это единственные высоты. Трудность максимальна.