给你 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$。是否可以将它们排列在一个圆上,使得每个数字都严格大于其两个邻居或严格小于其两个邻居?
换句话说,检查整数 $$$a_1, a_2, \ldots, a_n$$$ 是否存在重新排列 $$$b_1, b_2, \ldots, b_n$$$,使得对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$ 至少满足以下条件之一:
- $$$b_{i-1} < b_i > b_{i+1}$$$
- $$$b_{i-1} > b_i < b_{i+1}$$$
为了理解$$$i=1$$$和$$$i=n$$$的先前公式,应定义$$$b_0=b_n$$$和$$$b_{n+1}=b_1$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 3\cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^5$$$) — 整数的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果无法将符合语句条件的数字排列在圆上,则输出$$$\texttt{NO}$$$。您可以在任何情况下输出每个字母。
否则,输出$$$\texttt{YES}$$$。第二行输出 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$,它们是 $$$a_1, a_2, \ldots, a_n$$$ 的重新排列,并满足语句中的条件。如果有多种有效的数字排列方式,您可以输出其中任何一种。
示例
输入 #1
4 3 1 1 2 4 1 9 8 4 4 2 0 2 2 6 1 1 1 11 111 1111
输出 #1
NO YES 1 8 4 9 NO YES 1 11 1 111 1 1111
注意
可以看出,第一个和第三个测试用例没有有效的安排。
在第二个测试用例中,安排 $$$[1, 8, 4, 9]$$$ 有效。在这种排列中,$$$1$$$ 和 $$$4$$$ 都比它们的邻居小,而 $$$8、9$$$ 则更大。
在第四个测试用例中,安排 $$$[1, 11, 1, 111, 1, 1111]$$$ 有效。在这种排列中,等于 $$$1$$$ 的三个元素小于它们的邻居,而所有其他元素都大于它们的邻居。