Circular Local MiniMax
Contest: Codeforces Round 794 (Div. 1)
Difficulty rating: 1100
Tags: constructive algorithms, greedy, sortings

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} < b_i > b_{i+1}$$$
- $$$b_{i-1} > b_i < 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$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111

Example output:
NO
YES
1 8 4 9 
NO
YES
1 11 1 111 1 1111

Editorial:
Let's call $$$b_i$$$ local minimum if $$$b_{i-1} > b_i < b_{i+1}$$$ and local maximum if $$$b_{i-1} < b_i > b_{i+1}$$$. It's clear that in the arrangement satisfying the conditions from the statement, if $$$b_i$$$ is a local minimum, $$$b_{i+1}$$$ is a local maximum, and vice versa. Local minimums and local maximums will be alternating.
Then it's easy to see that such an arrangement can't exist for odd $$$n$$$. Indeed, suppose that the conditions from the statement are satisfied for $$$b_1, b_2, \ldots, b_n$$$. If we suppose that $$$b_1$$$ is local minimum, we get that $$$b_2$$$ is local maximum, $$$b_3$$$ is local minimum, $$$\ldots, $$$, $$$b_n$$$ is local minimum, $$$b_1$$$ is local maximum. Clearly, $$$b_1$$$ can't be a local maximum and a local minimum at the same time, leading to a contradiction.
Let's now consider the case of even $$$n = 2m$$$. Sort the array $$$a$$$, so that $$$a_1 \le a_2 \le \ldots \le a_{2m}$$$. Let's show that if $$$a_i = a_{i + m - 1} = x$$$ for some $$$2 \le i \le m-1$$$, then there is no arrangement satisfying the conditions from the statement. Indeed, consider such an arrangement: we have $$$m$$$ numbers $$$x$$$, and no two of them can be adjacent, so they occupy every second position. In addition, as local maximums and local minimums are alternating, we get that all $$$x$$$ are local maximums or all $$$x$$$ are local minimums. The first would imply that $$$a_{2m} < x$$$, which isn't possible. The second would imply that $$$a_1 > x$$$, which isn't possible.
It turns out that if there is no such $$$i$$$, the arrangement exists. Indeed, we can arrange numbers on the circle in the following order: $$$(a_1, a_{m+1}, a_2, a_{m+2}, \ldots, a_m, a_{2m})$$$. Here $$$a_k < a_{m + k} > a_{k+1}$$$ for $$$1 \le k \le m-1$$$, $$$a_{m+k} > a_{k+1} < a_{m+k+1}$$$ for $$$1 \le k \le m-1$$$, $$$a_{2m} > a_1 < a_{m+1}$$$ and $$$a_m < a_{2m} > a_1$$$.