CF1537C.Challenging Cliffs

You are a game designer and want to make an obstacle course. The player will walk from left to right. You have $n$ heights of mountains already selected and want to arrange them so that the absolute difference of the heights of the first and last mountains is as small as possible.

In addition, you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains $i$ ($1 \leq i \lt n$) such that $h_i \leq h_{i+1}$ where $h_i$ is the height of the $i$-th mountain. You don't want to waste any of the mountains you modelled, so you have to use all of them.

From all the arrangements that minimize $|h_1-h_n|$, find one that is the most difficult. If there are multiple orders that satisfy these requirements, you may find any.

你是一名游戏设计师，打算设计一个障碍赛道。玩家将从左向右行走。你已预先选定了 $n$ 座山的高度，现在希望将它们进行排列，使得第一座山与最后一座山的高度之差的绝对值 $|h_1 - h_n|$ 尽可能小。

此外，为了增加游戏难度，由于上坡或平路比下坡更难行走，关卡的难度定义为满足 $h_i \leq h_{i+1}$ 的山的个数（其中 $1 \leq i < n$），即非严格递增相邻对的个数；这里 $h_i$ 表示第 $i$ 座山的高度。你不想浪费任何已建模的山，因此必须使用全部 $n$ 座山。

在所有使 $|h_1 - h_n|$ 最小的排列中，找出一个难度最大的排列。若存在多个满足上述条件的排列，输出任意一个即可。

The first line will contain a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of mountains.

The second line of each test case contains $n$ integers $h_1,\ldots,h_n$ ($1 \leq h_i \leq 10^9$), where $h_i$ is the height of the $i$-th mountain.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, output $n$ integers — the given heights in an order that maximizes the difficulty score among all orders that minimize $|h_1-h_n|$.

If there are multiple orders that satisfy these requirements, you may output any.

对于每个测试用例，输出 $n$ 个整数——即给定的高度值，按某种顺序排列，使得在所有满足 $|h_1-h_n|$ 最小的排列中，该排列的难度得分最大。

若存在多个满足上述要求的排列，输出任意一个即可。

In the first test case:

The player begins at height $2$, next going up to height $4$ increasing the difficulty by $1$. After that he will go down to height $1$ and the difficulty doesn't change because he is going downhill. Finally the player will go up to height $2$ and the difficulty will increase by $1$. The absolute difference between the starting height and the end height is equal to $0$ and it's minimal. The difficulty is maximal.

In the second test case:

The player begins at height $1$, next going up to height $3$ increasing the difficulty by $1$. The absolute difference between the starting height and the end height is equal to $2$ and it's minimal as they are the only heights. The difficulty is maximal.

在第一个测试用例中：

玩家起始于高度 $2$，接着上升至高度 $4$，难度增加 $1$。随后，玩家下降至高度 $1$，由于是下坡，难度保持不变。最后，玩家上升至高度 $2$，难度再增加 $1$。起始高度与终点高度的绝对差值为 $0$，这是可能的最小值。此时难度达到最大。

在第二个测试用例中：

玩家起始于高度 $1$，接着上升至高度 $3$，难度增加 $1$。起始高度与终点高度的绝对差值为 $2$，由于仅有这两个高度，该差值已是最小可能值。此时难度达到最大。