CF1537C Challenging Cliffs

你是一名游戏设计师，想要制作一个障碍赛跑关卡。玩家将从左向右行进。你已经选定了 $n$ 座山的高度，并希望将它们排列，使得第一座和最后一座山的高度之差的绝对值尽可能小。 此外，你还希望让游戏更具挑战性。由于上坡或平地比下坡更难走，关卡的难度定义为满足 $h_i \leq h_{i+1}$ 的山峰数量 $i$（$1 \leq i < n$），其中 $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$），表示每座山的高度。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数，表示一种排列后的山峰高度顺序，使得在所有最小化 $|h_1-h_n|$ 的排列中，难度分数最大。 如果有多种满足要求的排列，你可以输出任意一种。

第一组测试数据： 玩家从高度 $2$ 开始，接着上升到高度 $4$，难度增加 $1$。之后下降到高度 $1$，难度不变，因为是下坡。最后上升到高度 $2$，难度再增加 $1$。起点和终点的高度差的绝对值为 $0$，且为最小值。难度也达到了最大。 第二组测试数据： 玩家从高度 $1$ 开始，接着上升到高度 $3$，难度增加 $1$。起点和终点的高度差的绝对值为 $2$，且为最小值，因为只有这两个高度。难度也达到了最大。 由 ChatGPT 4.1 翻译