您是一名游戏设计师,想要制作一个障碍训练场。玩家将从左向右行走。您已选择了 $$$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$$$ 并且它很小,因为它们是唯一的高度。难度是最大的。