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} < 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$$$.
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.
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$$$.
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.
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
readint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
readints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
readstr = lambda : sys.stdin.readline().rstrip('\r\n')
readstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())
readarri = lambda : [int(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
readarrs = lambda : [str(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
mod = 998244353
MOD = int(1000000000.0) + 7

def solve():
    n = readint()
    a = sorted(readints())
    b = []
    if n & 1:
        print('NO')
    else:
        i = 0
        j = n // 2
        while j < n:
            b.append(a[i])
            b.append(a[j])
            i += 1
            j += 1
        flg = True
        for i in range(n - 1):
            if b[i - 1] < b[i] > b[i + 1] or b[i - 1] > b[i] < b[i + 1]:
                continue
            else:
                flg = False
                break
        if flg:
            if b[n - 2] < b[n - 1] > b[0] or b[n - 2] > b[n - 1] < b[0]:
                print('YES')
                print(' '.join(map(str, b)))
            else:
                print('NO')
        else:
            print('NO')

def main():
    t = 1
    t = readint()
    for _ in range(t):
        solve()
if __name__ == '__main__':
    main()
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    a = list(map(int, inp().split()))
    if n % 2 == 1:
        print('NO')
        return
    a.sort()
    m = n // 2
    b = []
    for i in range(m):
        b.append(a[i])
        b.append(a[i + m])
    for i in range(1, n - 1):
        if not (b[i] < b[i + 1] and b[i] < b[i - 1] or (b[i] > b[i + 1] and b[i] > b[i - 1])):
            print('NO')
            return
    for i in (0, n - 1):
        if not (b[i] < b[(i + 1) % n] and b[i] < b[(i - 1) % n] or (b[i] > b[(i + 1) % n] and b[i] > b[(i - 1) % n])):
            print('NO')
            return
    print('YES')
    print(' '.join(map(str, b)))

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()
import sys
input = sys.stdin.readline
import math
''
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    s = a[:math.ceil(n / 2)]
    b = a[math.ceil(n / 2):]
    ans = [0] * n
    ans[::2] = s
    ans[1::2] = b
    if n % 2 != 0:
        print('NO')
        continue
    for i in range(n - 1):
        if ans[i] == ans[i + 1]:
            print('NO')
            break
    else:
        print('YES')
        print(*ans)