该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

挑战悬崖

题目描述

你是一位游戏设计师，你想要制作一条障碍赛道。其中玩家从左向右行走。

你已经选择了 $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

样例输入 #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$ ，且最小，因为它们是唯一的高度。难度最大。