## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Circular Local MiniMax Codeforces Solution | Codeforces Problem Solution 2022

C. Circular Local MiniMax
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $n$ integers ${a}_{1},{a}_{2},\dots ,{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},\dots ,{b}_{n}$ of the integers ${a}_{1},{a}_{2},\dots ,{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

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},\dots ,{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

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

Otherwise, output $\mathtt{\text{YES}}$. In the second line, output $n$ integers ${b}_{1},{b}_{2},\dots ,{b}_{n}$, which are a rearrangement of ${a}_{1},{a}_{2},\dots ,{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.