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-----

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-----

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

Otherwise, output ${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.


-----Examples-----

Input
4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111
Output
NO
YES
1 8 4 9 
NO
YES
1 11 1 111 1 1111


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

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Sorting

Constructive algorithms


Solutions:
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()
main()


cnt = int(input())
for i in range(cnt):
	num_cnt = int(input())
	num_str = input().split()
	if num_cnt % 2 != 0:
		print('NO')
		continue
	nums = list(map(int, num_str))
	nums.sort()
	right = len(nums) // 2
	new_nums = [nums[0], nums[right]]
	left = 1
	right += 1
	while right < len(nums):
		if new_nums[-1] <= nums[left] or nums[left] >= nums[right]:
			print('NO')
			break
		new_nums.append(nums[left])
		new_nums.append(nums[right])
		left += 1
		right += 1
	if len(new_nums) == len(nums):
		print('YES')
		print(' '.join(list(map(str, new_nums))))


import sys

def get():
	return [int(a) for a in sys.stdin.readline().strip().split()]
[t] = get()
for i in range(t):
	flag = 0
	[x] = get()
	ans = get()
	n = len(ans)
	ans.sort()
	a = ans[:int(len(ans) / 2)]
	b = ans[int(len(ans) / 2):]
	cnt = []
	for (i, j) in zip(a, b):
		cnt.append(i)
		cnt.append(j)
	if len(a) != len(b):
		print('NO')
		continue
	for i in range(len(ans)):
		l = i - 1
		r = (i + 1) % n
		if not (cnt[l] < cnt[i] and cnt[r] < cnt[i] or (cnt[l] > cnt[i] and cnt[r] > cnt[i])):
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')
		print(' '.join([str(x) for x in cnt]))


import sys
input = sys.stdin.readline
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	w = sorted(map(int, input().split()))
	if max(Counter(w).values()) > n // 2 or n % 2:
		print('NO')
	else:
		(i, j) = (0, n // 2)
		d = []
		while j != n:
			if i == n // 2:
				break
			d.append(w[i])
			i += 1
			d.append(w[j])
			j += 1
		for i in range(n):
			if not d[i - 1] < d[i] > d[i + 1 - n] and (not d[i - 1] > d[i] < d[i + 1 - n]):
				print('NO')
				break
		else:
			print('YES')
			print(' '.join(map(str, d)))


p = input
n = int(p())
for i in range(n):
	(s, d) = (int(p()), sorted(list(map(int, p().split(' ')))))
	m = (d[s // 2 - 1] + d[s // 2]) / 2
	print('YES\n' + ''.join([str(d[i]) + ' ' + str(d[s // 2 + i]) + ' ' for i in range(s // 2)])[:-1] if s % 2 == 0 and d.count(m) < s / 2 else 'NO')


t = int(input())

def makestring(nums, half):
	toreturn = ''
	for i in range(half):
		toreturn += str(nums[2 * half - 1 - i])
		toreturn += ' '
		toreturn += str(nums[half - 1 - i])
		toreturn += ' '
	return toreturn
for i in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	if n % 2 == 1:
		print('NO')
	else:
		nums.sort()
		half = int(n / 2)
		if nums[half - 1] != nums[half]:
			print('YES')
			print(makestring(nums, half))
		else:
			middle = nums[half]
			b = 0
			c = 0
			for j in range(half - 1, -1, -1):
				if nums[j] == middle:
					b += 1
				else:
					break
			for j in range(half, n, 1):
				if nums[j] == middle:
					c += 1
				else:
					break
			if b < half - c:
				print('YES')
				print(makestring(nums, half))
			else:
				print('NO')


def main():
	cas = int(input())
	for _ in range(cas):
		n = int(input())
		arr = list(map(int, input().split()))
		if n % 2:
			print('NO')
			continue
		arr.sort()
		flag = True
		m = int(n / 2)
		new_arr = []
		for i in range(m):
			new_arr.append(arr[i])
			new_arr.append(arr[m + i])
		new_arr.append(arr[0])
		for i in range(1, n):
			if i % 2 == 0 or new_arr[i - 1] < new_arr[i] > new_arr[i + 1]:
				continue
			flag = False
			break
		if flag:
			print('YES')
			print(' '.join(map(str, new_arr[:-1])))
		else:
			print('NO')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	m = int(n / 2)
	if n % 2:
		input()
		print('NO')
	else:
		a = [int(x) for x in input().split()]
		a.sort()
		if a[m - 1] < a[m]:
			print('YES')
			b = []
			for j in range(1, m + 1):
				b.append(a[-j])
				b.append(a[-j - m])
			print(' '.join((str(y) for y in b)))
		else:
			x = a[m]
			c1 = a[:m].count(x)
			c2 = a[m:].count(x)
			if c1 + c2 < m:
				print('YES')
				b = []
				for j in range(1, m + 1):
					b.append(a[-j])
					b.append(a[-j - m])
				print(' '.join((str(y) for y in b)))
			else:
				print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n % 2 == 1:
		print('NO')
	else:
		ans = []
		fg = True
		m = int(n / 2)
		for x in range(m):
			if a[x] == a[x + m - 1] and x != 0:
				print('NO')
				fg = False
				break
			ans.append(a[x])
			ans.append(a[x + m])
		if fg:
			print('YES')
			print(' '.join(map(str, ans)))


import sys

def checker(lst):
	for i in range(1, len(lst) - 1):
		if lst[i] > lst[i + 1] and lst[i] > lst[i - 1] or (lst[i] < lst[i + 1] and lst[i] < lst[i - 1]):
			pass
		else:
			return False
	if lst[0] > lst[-1] and lst[0] > lst[1] or (lst[0] < lst[-1] and lst[0] < lst[1]):
		pass
	else:
		return False
	if lst[-1] > lst[0] and lst[-1] > lst[-2] or (lst[-1] < lst[0] and lst[-1] < lst[-2]):
		pass
	else:
		return False
	return True
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	if n % 2 != 0:
		print('NO')
	else:
		arr.sort()
		i = 0
		j = n // 2
		res = []
		while j < n:
			res.append(arr[i])
			res.append(arr[j])
			i += 1
			j += 1
		if checker(res):
			print('YES')
			sys.stdout.write(' '.join(map(str, res)) + '\n')
		else:
			print('NO')


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if n & 1:
		print('NO')
		return
	a.sort()
	m = n // 2
	dp = []
	for i in range(m):
		if i < m - 1 and (a[i] == a[i + m] or a[i + 1] == a[i + m]) or (i == m - 1 and (a[i] == a[i + m] or a[0] == a[i + m])):
			print('NO')
			return
		dp += [a[i], a[i + m]]
	print('YES')
	print(*dp)
t = int(input())
for _ in range(t):
	solve()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li.sort()
	li2 = list()
	signal = 1
	if n % 2 == 1:
		signal = 0
	else:
		for i in range(1, n // 2):
			if li[i] == li[i + n // 2 - 1]:
				signal = 0
				break
	if signal == 0:
		print('NO')
	else:
		print('YES')
		m = n // 2
		for i in range(n // 2):
			li2.append(li[i])
			li2.append(li[m])
			m += 1
		print(*li2)


def check(ls, k):
	result = True
	for i in range(1, k - 1):
		if ls[i - 1] < ls[i] > ls[i + 1] or ls[i - 1] > ls[i] < ls[i + 1]:
			result = True
		else:
			return False
	return result and ls[0] < ls[-1]
t = int(input())
for el in range(t):
	k = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	out = []
	if k % 2 == 0:
		for i in range(k // 2):
			out.append(lst[i])
			out.append(lst[k // 2 + i])
		if check(out, k):
			print('YES')
			print(' '.join([str(s) for s in out]))
		else:
			print('NO')
	else:
		print('NO')


n = int(input())
for i in range(n):
	k = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if k % 2 == 1:
		print('NO')
		continue
	a1 = arr[:k // 2]
	b1 = arr[k // 2:]
	crr = []
	flag = 1
	for j in range(k // 2):
		crr.append(a1[j])
		crr.append(b1[j])
	for j in range(1, k, 2):
		if j != k - 1:
			if crr[j] > crr[j - 1] and crr[j] > crr[j + 1]:
				pass
			else:
				flag = 0
				break
	if flag == 1:
		if crr[-1] > crr[-2] and crr[-1] > crr[0]:
			print('YES')
			print(' '.join(map(str, crr)))
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n & 1:
		print('NO')
		continue
	a.sort()
	m = n // 2
	new_l = []
	for i in range(m):
		new_l.append(a[i])
		new_l.append(a[i + m])
	for i in range(1, n, 2):
		if not new_l[i - 1] < new_l[i] > new_l[(i + 1) % n]:
			print('NO')
			break
	else:
		print('YES')
		print(' '.join(map(str, new_l)))


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 != 0:
		print('NO')
		return
	else:
		arr.sort()
		brr = arr[:n // 2]
		crr = arr[n // 2:]
		ans = []
		for i in range(n // 2):
			ans += [brr[i]]
			ans += [crr[i]]
		for i in range(1, n - 1):
			if ans[i] < ans[i + 1] and ans[i] < ans[i - 1] or (ans[i] > ans[i + 1] and ans[i] > ans[i - 1]):
				continue
			else:
				print('NO')
				return
		if not (ans[0] < ans[1] and ans[0] < ans[-1] or (ans[0] > ans[1] and ans[0] > ans[-1])):
			print('NO')
			return
		if not (ans[-1] > ans[0] and ans[-1] > ans[-2] or (ans[-1] < ans[-2] and ans[-1] < ans[0])):
			print('NO')
			return
		print('YES')
		print(' '.join((str(ele) for ele in ans)))
while t:
	solve()
	t -= 1


def check(left, center, right):
	return True if left > center and center < right or (left < center and center > right) else False

def find(n, a):
	if n % 2 == 1:
		return []
	a.sort()
	a.reverse()
	high = a[:int(n / 2)]
	low = a[int(n / 2):]
	combine = [a[-1]]
	for i in range(int(n / 2)):
		combine.append(high[i])
		combine.append(low[i])
	combine.append(a[0])
	for ind in range(1, n + 1):
		if not check(combine[ind - 1], combine[ind], combine[ind + 1]):
			return []
	return combine
case = int(input())
for _ in range(case):
	n = int(input())
	line = input().split()
	a = [int(elem) for elem in line]
	ans = find(n, a)
	ans_str = [str(elem) for elem in ans]
	if ans:
		print('YES')
		ans_str.pop()
		ans_str.pop(0)
		print(' '.join(ans_str))
	else:
		print('NO')


numb = int(input())
for h in range(numb):
	ll = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if ll % 2 == 1:
		print('NO')
	else:
		d = 0
		m = [l[0], l[0 + ll // 2]]
		for i in range(1, ll // 2):
			k1 = l[i]
			k2 = l[i + ll // 2]
			if k1 != k2 and m[-1] != k1:
				m.append(l[i])
				m.append(l[i + ll // 2])
			else:
				d = 1
				break
		if d == 1:
			print('NO')
		else:
			print('YES')
			print(*m)


import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	a = n // 2
	if n % 2 == 1:
		print('NO')
	else:
		dp = []
		for i in range(a):
			dp += [l[i], l[i + a]]
			if i != a - 1 and (l[i] == l[i + a] or l[i + 1] == l[i + a]):
				print('NO')
				break
			elif i == a - 1 and (l[i] == l[i + a] or l[0] == l[i + a]):
				print('NO')
				break
		else:
			print('YES')
			print(*dp)


t = int(input())
while t >= 1:
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 != 0:
		print('NO')
	else:
		a.sort()
		bool = True
		ans = []
		for i in range(n // 2):
			ans.append(a[i])
			ans.append(a[i + n // 2])
		for i in range(1, len(ans), 2):
			if ans[i] > ans[(i - 1) % n] and ans[i] > ans[(i + 1) % n]:
				continue
			else:
				bool = False
				break
		if bool == False:
			print('NO')
		else:
			print('YES')
			print(*ans)
	t -= 1


t = int(input())
for i in range(t):
	x = int(input())
	a = list(map(int, input().split()))
	if x % 2 == 1:
		print('NO')
	else:
		a.sort()
		b = []
		check = True
		for j in range(x // 2):
			if a[0 + j] != a[x // 2 + j]:
				b.append(a[0 + j])
				b.append(a[x // 2 + j])
				if j > 0 and b[j * 2] == b[j * 2 - 1]:
					print('NO')
					check = False
					break
			else:
				print('NO')
				check = False
				break
		if check:
			print('YES')
			print(*b)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	case = True
	if n % 2 == 0:
		ans = []
		for i in range(n // 2):
			ans.append(a[i])
			ans.append(a[n // 2 + i])
			if ans[-1] == ans[-2] or (len(ans) > 2 and ans[-3] == ans[-2]):
				case = False
				break
	else:
		case = False
	if case:
		print('YES')
		print(*ans)
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	if n % 2:
		print('NO')
		continue
	nums.sort()
	ans = []
	flag = 1
	for i in range(n // 2):
		if i and nums[i] == nums[n // 2 + i - 1]:
			print('NO')
			flag = 0
			break
		ans.extend([nums[i], nums[n // 2 + i]])
	if flag:
		print('YES')
		print(*ans)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	lans = []
	flag = 1
	l.sort()
	if n % 2 == 1:
		flag = 0
	else:
		for i in range(1, n // 2):
			if l[i] == l[i + n // 2 - 1]:
				flag = 0
				break
	if flag:
		print('YES')
		for i in range(n):
			if i % 2 == 0:
				lans.insert(i, l[i // 2])
			else:
				lans.insert(i, l[n // 2 + i // 2])
		print(*lans)
	else:
		print('NO')
	t -= 1


for j in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 != 0:
		print('NO')
	else:
		ans = 'YES'
		l.sort()
		l1 = l[0:n // 2]
		l2 = l[n // 2:]
		l3 = []
		for i in range(0, n // 2):
			l3.append(l1[i])
			l3.append(l2[i])
		for x in range(0, n - 1):
			if l3[x] == l3[x + 1]:
				ans = 'NO'
				break
		if ans == 'NO':
			print('NO')
		else:
			print('YES')
			print(*l3)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	if n % 2 == 1:
		print('NO')
		continue
	l.sort()
	k = n // 2
	z = []
	if l[k] > l[0] and l[-1] > l[0]:
		z.append(l[0])
		z.append(l[k])
	else:
		print('NO')
		continue
	flag = True
	for i in range(1, k):
		if l[i] < l[i + k] and l[i] < l[i + k - 1]:
			z.append(l[i])
			z.append(l[i + k])
		else:
			print('NO')
			flag = False
			break
	if flag == True:
		print('YES')
		print(*z)


n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	if x % 2 == 1:
		print('NO')
	else:
		l = sorted(l)
		m = (l[x // 2 - 1] + l[x // 2]) / 2
		if l.count(m) < x / 2:
			print('YES')
			for k in range(x // 2):
				print(str(l[k]) + ' ' + str(l[x // 2 + k]) + ' ', end='')
				if k == x // 2 - 1:
					print('')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(s) for s in input().split()]
	if n % 2 != 0:
		print('NO')
	else:
		a.sort()
		flag = True
		b = [0] * n
		b[0] = a[0]
		for i in range(1, n // 2):
			d = i * 2
			if a[i] < a[i + n // 2 - 1]:
				b[d] = a[i]
				b[d - 1] = a[i + n // 2 - 1]
			else:
				flag = False
				break
		if flag:
			b[-1] = a[-1]
			print('YES')
			print(*b)
		else:
			print('NO')


T = int(input())
for _ in range(T):
	n = int(input())
	s = list(map(int, input().split()))
	s = sorted(s, reverse=False)
	marker = True
	ans = []
	mid = n // 2
	if n % 2 == 0:
		if s[mid] == s[mid - 1] and s.count(s[mid]) >= n // 2:
			print('NO')
		else:
			for i in range(n // 2):
				ans.extend([s[i], s[i + n // 2]])
			print('YES')
			print(*ans)
	else:
		print('NO')


casos = int(input())
while casos > 0:
	casos -= 1
	cantidad = int(input())
	w = cantidad // 2
	V = True
	guardias = input().split()
	arreglo = [int(x) for x in guardias]
	arreglo.sort()
	if cantidad % 2 == 0:
		V = False
		for i in range(1, w):
			if (arreglo[i + w] and arreglo[i + w - 1]) <= arreglo[i]:
				V = True
				break
		if arreglo[0] >= arreglo[w]:
			V = True
		if V == False:
			print('YES')
			for i in range(w - 1):
				print(arreglo[i], arreglo[w + i], end=' ')
			print(arreglo[-1 - w], arreglo[-1])
	if V:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 == 1:
		print('NO')
	else:
		l.sort()
		a = 0
		k = []
		while a < n // 2:
			k.append(l[a])
			k.append(l[a + n // 2])
			a += 1
		if any((k[i] == k[i + 1] for i in range(len(k) - 1))):
			print('NO')
		else:
			print('YES')
			print(*k)


import sys
input = sys.stdin.readline

def solve():
	(N, A) = (int(input()), list(map(int, input().split())))
	A.sort()
	i = 0
	j = N // 2
	B = []
	while i < N // 2 or j < N:
		if i <= N // 2:
			B.append(A[i])
			i += 1
		if j < N:
			B.append(A[j])
			j += 1
	if not (B[N - 1] < B[0] and B[0] > B[1] or (B[N - 1] > B[0] and B[0] < B[1])):
		print('NO')
		return
	if not (B[N - 2] < B[N - 1] and B[N - 1] > B[0] or (B[N - 2] > B[N - 1] and B[N - 1] < B[0])):
		print('NO')
		return
	for i in range(1, N - 1):
		if not (B[i - 1] < B[i] and B[i] > B[i + 1] or (B[i - 1] > B[i] and B[i] < B[i + 1])):
			print('NO')
			return
	print('YES')
	print(*B)
for _ in range(int(input())):
	solve()


for t in range(int(input())):
	n = int(input())
	arr = sorted(map(int, input().split()))
	case = True
	if n % 2 == 0:
		ans = []
		for i in range(n // 2):
			ans.append(arr[i])
			ans.append(arr[n // 2 + i])
			if ans[-1] == ans[-2] or (len(ans) > 2 and ans[-3] == ans[-2]):
				case = False
				break
	else:
		case = False
	if case:
		print('YES')
		print(*ans)
	else:
		print('NO')


def cir():
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2 != 0:
		print('NO')
		return
	else:
		lst = []
		l.sort()
		i = 0
		j = n // 2
		while j < n:
			if l[i] == l[j]:
				print('NO')
				return
			elif len(lst) != 0 and l[i] == lst[-1]:
				print('NO')
				return
			else:
				lst.append(l[i])
				lst.append(l[j])
				i = i + 1
				j = j + 1
		print('YES')
		print(*lst)
t = int(input())
while t:
	cir()
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	if n % 2 == 1:
		print('NO')
	else:
		a = sorted(a)
		mid = n // 2
		ans = []
		check = True
		for i in range(mid):
			if ans and a[i] == ans[-1]:
				check = False
				break
			else:
				ans.append(a[i])
			if a[i + mid] == ans[-1]:
				check = False
				break
			else:
				ans.append(a[i + mid])
		if not check:
			print('NO')
		else:
			print('YES')
			print(*ans)


times = int(input())
for time in range(times):
	n = int(input())
	numbers = input().split()
	if n % 2 == 1:
		print('NO')
		continue
	k = n // 2
	for j in range(n):
		numbers[j] = int(numbers[j])
	numbers.sort()
	if numbers[k] != numbers[k - 1]:
		print('YES')
		new_numbers = []
		for j in range(k):
			new_numbers.append(numbers[j])
			new_numbers.append(numbers[j + k])
		print(*(new_numbers[j] for j in range(n)))
		continue
	a = numbers[k]
	for j in range(k):
		if numbers[j] == a:
			break
	for i in range(k, n):
		if numbers[i] != a:
			i -= 1
			break
	if not i - j + 2 > k:
		print('YES')
		new_numbers = []
		for j in range(k):
			new_numbers.append(numbers[j])
			new_numbers.append(numbers[j + k])
		print(*(new_numbers[j] for j in range(n)))
		continue
	print('NO')


import math
for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	if n % 2 == 1:
		print('NO')
	else:
		A.sort()
		a = A[:n // 2]
		b = A[n // 2:]
		q = []
		for k in range(n // 2):
			q.append(a[k])
			q.append(b[k])
		for j in range(n - 1):
			if q[j] == q[j + 1]:
				print('NO')
				break
		else:
			print('YES')
			print(*q)


def circular(arr, n):
	ok = 1
	if n % 2 == 1:
		ok = 0
		print('NO')
	else:
		arr = sorted(arr)
		arr2 = []
		i = 0
		l = int(n / 2)
		while i < l:
			if i < l - 1:
				if arr[i + 1] >= arr[i + l]:
					check = 1
				else:
					check = 0
			if arr[i] >= arr[i + l] or check:
				print('NO')
				ok = 0
				break
			else:
				arr2.append(arr[i])
				arr2.append(arr[i + l])
				i += 1
		if ok == 1:
			print('YES')
			print(*arr2, sep=' ')
t = int(input())
for j in range(t):
	n = int(input())
	arr = input().split(' ')
	for i in range(n):
		arr[i] = int(arr[i])
	circular(arr, n)


I = lambda : [int(i) for i in input().split()]
for _ in range(I()[0]):
	(n,) = I()
	l = sorted(I())
	if n % 2 == 1:
		print('NO')
		continue
	(l1, l2) = (l[:n // 2], l[n // 2:])
	ans = []
	for i in range(n // 2):
		ans.append(l1[i])
		ans.append(l2[i])
	ok = True
	curr = ans[0]
	for i in ans[1:]:
		if i == curr:
			ok = False
			break
		curr = i
	if ok:
		print('YES')
		print(*ans)
	else:
		print('NO')


import collections
x = int(input())

def cal(n, p):
	if n % 2 == 1:
		return ['NO', '']
	p.sort()
	c = collections.Counter(p)
	for tt in c.keys():
		if c[tt] > n // 2:
			return ['NO', '']
		elif c[tt] == n // 2:
			if tt not in [max(p), min(p)]:
				return ['NO', '']
	k = []
	for i in range(n // 2):
		k.append(str(p[i]))
		k.append(str(p[i + n // 2]))
	return ['YES', ' '.join(k)]
for jj in range(x):
	n = int(input())
	p = [int(i) for i in input().split(' ')]
	(a, b) = cal(n, p)
	if a == 'NO':
		print(a)
	else:
		print(a)
		print(b)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	ans = 1
	l = []
	if n % 2 or a[0] == a[-1]:
		print('NO')
	else:
		for i in range(n // 2):
			l.append(a[i])
			l.append(a[n // 2 + i])
			if a[i] == a[n // 2 + i] or (a[i] == a[n // 2 + i - 1] and i > 0):
				ans = 0
				break
		if ans == 1:
			print('YES')
			print(*l)
		else:
			print('NO')


def test_seq(up, low):
	for i in range(len(up)):
		if not (up[i] > low[i] and up[(i + 1) % len(up)] > low[i]):
			return False
	return True

def print_seq(up, low):
	print('YES')
	for (i, j) in zip(up, low):
		print(i, end=' ')
		print(j, end=' ')
	print()

def solve():
	input()
	nums = list(sorted(map(int, input().split())))
	if len(nums) % 2 == 1:
		print('NO')
		return
	low = nums[:len(nums) // 2]
	up = nums[len(nums) // 2:]
	if test_seq(up, low):
		print_seq(up, low)
		return
	up = up[-1:] + up[:-1]
	if test_seq(up, low):
		print_seq(up, low)
		return
	print('NO')
	return
n = int(input())
for i in range(n):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if len(a) % 2 != 0:
		print('NO')
	else:
		a = sorted(a)
		mid = int(n / 2)
		flag = False
		ans = []
		for i in range(mid):
			if a[i] >= a[i + mid]:
				flag = True
				break
			else:
				if ans:
					if ans[-1] <= a[i]:
						flag = True
						break
				ans.append(a[i])
				ans.append(a[i + mid])
		if flag:
			print('NO')
		else:
			print('YES')
			print(*ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n % 2 == 1:
		print('NO')
	else:
		sarr = sorted(arr)
		max_freq = 1
		itr_freq = 1
		val = sarr[0]
		for i in range(1, n):
			if sarr[i] == sarr[i - 1]:
				itr_freq += 1
				if itr_freq > max_freq:
					max_freq = itr_freq
					val = sarr[i]
			else:
				itr_freq = 1
		if max_freq > n / 2:
			print('NO')
		elif max_freq == n / 2:
			if val == sarr[0] or val == sarr[n - 1]:
				ans = []
				for i in sarr:
					if i != val:
						ans.append(val)
						ans.append(i)
				print('YES')
				print(*ans)
			else:
				print('NO')
		else:
			print('YES')
			ans = []
			for i in range(n // 2):
				ans.append(sarr[i])
				ans.append(sarr[i + n // 2])
			print(*ans)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2:
		print('NO')
		return
	ans = []
	arr.sort()
	large = n // 2
	for i in range(n - 1):
		if i % 2 == 0:
			ans.append(arr[large])
			large += 1
		else:
			ans.append(arr[1 + i // 2])
	ans.append(arr[0])
	for i in range(n):
		if ans[i - 1] < ans[i] and ans[i] > ans[(i + 1) % n] or (ans[i - 1] > ans[i] and ans[i] < ans[(i + 1) % n]):
			continue
		print('NO')
		return
	print('YES')
	print(*ans)
	return
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n % 2:
		print('NO')
	else:
		l.sort()
		mnl = l[:n // 2]
		mxl = l[n // 2:]
		i = 0
		ans = []
		while i != n // 2:
			ans.append(mnl[i])
			ans.append(mxl[i])
			i += 1
		for i in range(0, n, 2):
			if not ans[i - 1] > ans[i] < ans[i + 1]:
				print('NO')
				break
		else:
			print('YES')
			print(*ans)


def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		arr = [int(a) for a in input().split()]
		arr.sort()
		arr2 = []
		for i in range(n // 2):
			arr2.append(arr[i])
			arr2.append(arr[i + n // 2])
		if n % 2:
			arr2.append(arr[n - 1])
		flag = 1
		for i in range(1, n):
			if arr2[i] <= arr2[i - 1] and arr2[i] >= arr2[(i + 1) % n]:
				flag = -1
				break
			if arr2[i] >= arr2[i - 1] and arr2[i] <= arr2[(i + 1) % n]:
				flag = -1
				break
		if flag == -1:
			print('NO')
		else:
			print('YES')
			if n % 2:
				print(*arr2[:-1])
			else:
				print(*arr2)
main()


t = int(input())
for i in range(t):
	n = int(input())
	m = [int(x) for x in input().split()]
	m.sort()
	flag = False
	if n % 2 == 0:
		h = []
		for k in range(n // 2):
			h.append(m[k])
			h.append(m[n // 2 + k])
		for i in range(len(h) - 1):
			if h[i] == h[i + 1]:
				print('NO')
				flag = True
				break
		if not flag:
			print('YES')
			for j in range(len(h)):
				print(h[j], end=' ')
			print()
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = []
	if n % 2 == 1:
		print('NO')
	else:
		for i in range(0, n // 2):
			ans.append(a[i])
			ans.append(a[n // 2 + i])
		if n % 2 == 1:
			ans.append(n // 2)
		var = 1
		for i in range(n - 1):
			if ans[i] == ans[i + 1]:
				var = 0
			if i == n - 2:
				if ans[i + 1] == a[0]:
					var = 0
		if var:
			print('YES')
			print(*ans)
		else:
			print('NO')


def readArr():
	return [int(x) for x in input().split()]

def solve():
	N = int(input())
	a = readArr()
	if N & 1:
		print('NO')
		return
	a.sort(reverse=True)
	a1 = a[:N // 2]
	a2 = a[N // 2:]
	b = []
	for i in range(N // 2):
		b.append(a1[i])
		b.append(a2[i])
	for i in range(N):
		prev = (i - 1) % N
		nxt = (i + 1) % N
		cond1 = b[prev] < b[i] and b[nxt] < b[i]
		cond2 = b[prev] > b[i] and b[nxt] > b[i]
		if not (cond1 or cond2):
			print('NO')
			return
	print('YES')
	print(*b)
T = int(input())
for _ in range(T):
	solve()


for i in range(int(input())):
	a = int(input())
	b = sorted(list(map(int, input().split())))
	c = 0
	if a % 2 == 0:
		for j in range(a // 2):
			if b[j] < b[j + a // 2] and b[j + a // 2] > b[(j + 1) % (a // 2)]:
				c = 0
			else:
				c += 1
				break
	if c == 1 or a % 2 == 1:
		print('NO')
	else:
		print('YES')
		for j in range(a // 2):
			print(b[j], b[j + a // 2], end=' ')
		print()


def solve():
	n = int(input())
	arr = list(map(int, input().split(' ')))
	if n % 2 == 1:
		print('NO')
		return
	arr.sort()
	b = [0] * len(arr)
	j = 0
	for i in range(0, int(len(arr) / 2)):
		b[j] = arr[i]
		j += 2
	j = 1
	for i in range(int(len(arr) / 2), len(arr), 1):
		b[j] = arr[i]
		j += 2
	for i in range(1, len(arr) - 1):
		if b[i] >= b[i + 1] and b[i] <= b[i - 1]:
			print('NO')
			return
		if b[i] >= b[i - 1] and b[i] <= b[i + 1]:
			print('NO')
			return
	print('YES')
	for ele in b:
		print(ele, end=' ')
	print()
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	(n, a, x, bad) = (int(input()), [int(x) for x in input().split()], [], False)
	if n % 2 == 0:
		a.sort()
		n = n // 2
		for i in range(n - 1):
			if not a[i + 1] == a[i + n]:
				x.append(a[i])
				x.append(a[i + n])
			else:
				bad = True
		i += 1
		if not a[i] == a[i + n]:
			x.append(a[i])
			x.append(a[i + n])
		if not bad:
			print('YES')
			for d in x:
				print(d, end=' ')
			print('')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	arr = [0 for _ in range(n)]
	a.sort()
	if n % 2:
		print('NO')
		continue
	pos = 0
	for i in range(n - 1, n // 2 - 1, -1):
		arr[pos] = a[i]
		pos += 2
	pos = 1
	for i in range(n // 2 - 1, -1, -1):
		arr[pos] = a[i]
		pos += 2
	f = 1
	for i in range(1, n - 1):
		if arr[i] == arr[i - 1]:
			f = 0
			break
	if f:
		print('YES')
		print(*arr)
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if n % 2 == 0:
		k = n // 2
		s1 = l[0:k]
		s2 = l[k:]
		sam = []
		for i in range(k):
			sam.append(s1[i])
			sam.append(s2[i])
	else:
		k = n // 2
		s1 = l[0:k + 1]
		s2 = l[k + 1:]
		sam = []
		for i in range(k):
			sam.append(s1[i])
			sam.append(s2[i])
		sam.append(s1[k])
	if sam[0] == sam[-1]:
		print('NO')
	elif sam[-1] < sam[-2] and sam[-1] > sam[0]:
		print('NO')
	else:
		k = 0
		for i in range(n - 1):
			if sam[i] == sam[i + 1]:
				k = 1
				print('NO')
				break
		if k == 0:
			print('YES')
			print(*sam)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == 1:
		print('NO')
	else:
		a.sort()
		res = []
		x = 0
		y = n // 2
		for i in range(n):
			if i % 2 == 0:
				res.append(a[x])
				x += 1
			else:
				res.append(a[y])
				y += 1
		ans = True
		for i in range(0, n - 1, 2):
			if res[i] >= res[i - 1] or res[i] >= res[i + 1]:
				ans = False
				break
		if ans:
			print('YES')
			print(*res)
		else:
			print('NO')


t = int(input())

def pairs_in_list(l):
	ans = []
	for i in range(len(l) - 1):
		if l[i] < l[i + 1]:
			ans.append(0)
		elif l[i] == l[i + 1]:
			ans.append(0.5)
		else:
			ans.append(1)
	if l[-1] < l[0]:
		ans.append(0)
	elif l[-1] == l[0]:
		ans.append(0.5)
	else:
		ans.append(1)
	return ans
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	if n % 2 == 1:
		res = 'NO'
	else:
		m = n // 2
		l1 = l[:m]
		l2 = l[m:]
		l3 = []
		for k in range(m):
			l3.append(l1[k])
			l3.append(l2[k])
		if pairs_in_list(l3) == [0, 1] * m:
			res = 'YES'
		else:
			res = 'NO'
	if res == 'YES':
		print(res)
		print(*l3)
	else:
		print(res)