← 返回题目列表

Codeforces · 1537/C

C. 具有挑战性的悬崖

中文机器翻译题面 查看原题

您是一名游戏设计师,想要制作一个障碍训练场。玩家将从左向右行走。您已选择了 $$$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|$$$ 的所有订单中最大化难度分数。

如果有多个订单满足这些要求,则可以输出任何一个。

示例

输入 #1

2
4
4 2 1 2
2
3 1

输出 #1

2 4 1 2 
1 3

注意

在第一个测试用例中:

玩家从高度 $$$2$$$ 开始,接下来上升到高度 $$$4$$$,难度增加 $$$1$$$。之后他会下降到高度 $$$1$$$ 并且难度不会改变,因为他正在下坡。最后玩家将上升到高度$$$2$$$,难度将增加$$$1$$$。起始高度和结束高度之间的绝对差等于 $$$0$$$ 并且最小。难度是最大的。

在第二个测试用例中:

玩家从高度 $$$1$$$ 开始,接下来上升到高度 $$$3$$$,难度增加 $$$1$$$。起始高度和结束高度之间的绝对差等于 $$$2$$$ 并且它很小,因为它们是唯一的高度。难度是最大的。