CF1685A.Circular Local MiniMax

You are given $n$ integers $a_1, a_2, \ldots, a_n$. Is it possible to arrange them on a circle so that each number is strictly greater than both its neighbors or strictly smaller than both its neighbors?

In other words, check if there exists a rearrangement $b_1, b_2, \ldots, b_n$ of the integers $a_1, a_2, \ldots, a_n$ such that for each $i$ from $1$ to $n$ at least one of the following conditions holds:

• $b_{i-1} \lt b_i \gt b_{i+1}$
• $b_{i-1} \gt b_i \lt b_{i+1}$

To make sense of the previous formulas for $i=1$ and $i=n$, one shall define $b_0=b_n$ and $b_{n+1}=b_1$.

给你 $n$ 个整数 $a_1, a_2, \ldots, a_n$。是否可以将它们排成一个圆圈，使得每个数都严格大于它的两个相邻数，或严格小于它的两个相邻数？

换句话说，请判断是否存在 $a_1, a_2, \ldots, a_n$ 的一个重排 $b_1, b_2, \ldots, b_n$，使得对每个 $i$（从 $1$ 到 $n$），以下两个条件中至少有一个成立：

• $b_{i-1} \lt b_i \gt b_{i+1}$
• $b_{i-1} \gt b_i \lt b_{i+1}$

为使上述公式在 $i=1$ 和 $i=n$ 时有意义，定义 $b_0 = b_n$ 且 $b_{n+1} = b_1$。

The first line of the input contains a single integer $t$ ($1 \le t \le 3\cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 10^5$) — the number of integers.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).

The sum of $n$ over all test cases doesn't exceed $2\cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, if it is not possible to arrange the numbers on the circle satisfying the conditions from the statement, output $\texttt{NO}$. You can output each letter in any case.

Otherwise, output $\texttt{YES}$. In the second line, output $n$ integers $b_1, b_2, \ldots, b_n$, which are a rearrangement of $a_1, a_2, \ldots, a_n$ and satisfy the conditions from the statement. If there are multiple valid ways to arrange the numbers, you can output any of them.

对于每个测试用例，若无法将数字按题目所述条件排列成一个环，则输出 $\texttt{NO}$。其中每个字母的大小写均可。

否则，输出 $\texttt{YES}$。在第二行输出 $n$ 个整数 $b_1, b_2, \ldots, b_n$，它们是 $a_1, a_2, \ldots, a_n$ 的一个重排，且满足题目所述条件。若存在多种合法的排列方式，输出任意一种即可。

It can be shown that there are no valid arrangements for the first and the third test cases.

In the second test case, the arrangement $[1, 8, 4, 9]$ works. In this arrangement, $1$ and $4$ are both smaller than their neighbors, and $8, 9$ are larger.

In the fourth test case, the arrangement $[1, 11, 1, 111, 1, 1111]$ works. In this arrangement, the three elements equal to $1$ are smaller than their neighbors, while all other elements are larger than their neighbors.

可以证明，第一个和第三个测试用例不存在合法的排列。

在第二个测试用例中，排列 $[1, 8, 4, 9]$ 是可行的。在此排列中，$1$ 和 $4$ 均小于其相邻元素，而 $8$ 和 $9$ 均大于其相邻元素。

在第四个测试用例中，排列 $[1, 11, 1, 111, 1, 1111]$ 是可行的。在此排列中，三个值为 $1$ 的元素均小于其相邻元素，而所有其他元素均大于其相邻元素。