题目描述

给你 $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$）。($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$的重新排列，并且满足语句中的条件。如果有多种有效的数字排列方式，可以输出任意一种。

样例

4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111

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$相等的三个元素都小于它们的邻近元素，而所有其他元素都大于它们的邻近元素。