You are given an array A of N integers A_{1}, A_{2}, \ldots, A_{N}. Determine if there are two [permutations] B and C of this array, for which the following condition is satisfied:

* There doesn't exist a pair of integers (i, j) such that 1 ≤ i ≤ j ≤ N and (i, j) \neq (1, N), for which the subarray B[i:j] is a permutation of subarray C[i:j].

If there exist such permutations, find any of them.

As a reminder, B[i:j] refers to the subarray [B_{i}, B_{i+1}, \ldots, B_{j}]

------ Input Format ------ 

- The first line of the input contains a single integer T, the number of test cases. The description of the test cases follows.
- The first line of each test case contains a single integer N — the number of integers.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, if there are no such permutations B and C, output NO.

Otherwise, on the first line output YES. In the next line, output N integers B_{1}, B_{2}, \ldots, B_{N}. In the next line, output N integers C_{1}, C_{2}, \ldots, C_{N}.

You may print each character of YES/NO in either uppercase or lowercase (for example, the strings YES, yeS, YeS, and yEs will all be treated as identical).

------ Constraints ------ 

$1 ≤T ≤100$
$3 ≤N ≤1000$
$0 ≤A_{i} ≤10^{9}$
- The sum of $N$ over all test cases doesn't exceed $2000$.

----- Sample Input 1 ------ 
3
3
1 1 2
4
19 39 19 84
6
1 2 3 1 2 3
----- Sample Output 1 ------ 
NO
YES
19 19 39 84 
39 84 19 19 
YES
1 1 2 2 3 3 
2 3 3 1 1 2 
----- explanation 1 ------ 
Test case $1$: There are $3 \times 3 = 9$ pairs of permutations of the given array. Here's why they're all bad:
- If $B = [1, 1, 2]$ and $C = [1, 1, 2]$, $B[1:1] = C[1:1]$
- If $B = [1, 1, 2]$ and $C = [1, 2, 1]$, $B[1:1] = C[1:1]$
- If $B = [1, 1, 2]$ and $C = [2, 1, 1]$, $B[2:2] = C[2:2]$
- If $B = [1, 2, 1]$ and $C = [1, 1, 2]$, $B[1:1] = C[1:1]$
- If $B = [1, 2, 1]$ and $C = [1, 2, 1]$, $B[1:1] = C[1:1]$
- If $B = [1, 2, 1]$ and $C = [2, 1, 1]$, $B[3:3] = C[3:3]$
- If $B = [2, 1, 1]$ and $C = [1, 1, 2]$, $B[2:2] = C[2:2]$
- If $B = [2, 1, 1]$ and $C = [1, 2, 1]$, $B[3:3] = C[3:3]$
- If $B = [2, 1, 1]$ and $C = [2, 1, 1]$, $B[1:1] = C[1:1]$

Source: codechef | Difficulty: HARD
Tags: Sorting

Constructive algorithms


Solutions:
from math import ceil, log, floor, sqrt, gcd
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = {}
	for i in l:
		try:
			f[i] += 1
		except:
			f[i] = 1
	if max(f.values()) > n // 2 or len(set(l)) <= 2:
		print('NO')
	else:
		print('YES')
		l.sort()
		print(*l)
		print(*l[n // 2:] + l[:n // 2])


import math
import bisect
import heapq
from math import gcd, floor, sqrt, log
from collections import defaultdict as ddc
from collections import Counter

def intin():
	return int(input())

def mapin():
	return map(int, input().split())

def strin():
	return input().split()
INF = 10 ** 20
mod = 1000000007

def exponentiation(bas, exp, mod=1000000007):
	t = 1
	while exp > 0:
		if exp % 2 != 0:
			t = t * bas % mod
		bas = bas * bas % mod
		exp //= 2
	return t % mod

def MOD(p, q=1, mod=1000000007):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def process(arr, n):
	C = Counter(arr)
	edge = 0
	for val in C.values():
		if val > n // 2:
			print('NO')
			return
		elif val == n // 2:
			edge += 1
	if len(C.keys()) == edge == 2:
		print('NO')
		return
	print('YES')
	arr.sort()
	(B, C) = (arr, arr[(n + 1) // 2:] + arr[:(n + 1) // 2])
	r = n - 1
	for i in range(n):
		if i >= r:
			break
		if B[i] == C[i]:
			(C[i], C[r]) = (C[r], C[i])
			r -= 1
	print(*B)
	print(*C)

def main():
	for _ in range(int(input())):
		n = intin()
		arr = list(mapin())
		process(arr, n)
main()


tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		try:
			d[i] += 1
		except KeyError:
			d[i] = 1
	m = max(list(d.values()))
	k = len(list(d.keys()))
	if m > n // 2 or k <= 2:
		print('NO')
		continue
	else:
		print('YES')
		a.sort()
		print(*a)
		print(*a[m:] + a[:m])


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
			else:
				c += 2
		i += 1
	return c

def ncr_modulo(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return len(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def calc(s):
	ans = 0
	for ele in s:
		ans += ord(ele) - 96
	return ans

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def solve():
	n = int(input())
	d = defaultdict(lambda : 0)
	l = list(map(int, input().split()))
	ans = []
	for ele in l:
		d[ele] += 1
	if len(d) <= 2:
		print('NO')
		return
	l = sorted(d.items(), key=lambda kv: (kv[1], kv[0]), reverse=True)
	for ele in l:
		if ele[1] > n // 2:
			print('NO')
			return
		else:
			break
	ans1 = [l[0][0] for _ in range(l[0][1])]
	ans2 = [l[0][0] for _ in range(l[0][1])]
	temp1 = []
	for i in range(1, len(l)):
		temp1 += [l[i][0] for _ in range(l[i][1])]
	ans1 += temp1
	ans2 = temp1 + ans2
	print('YES')
	print(*ans1)
	print(*ans2)
for _ in range(int(input())):
	solve()


def go():
	for i in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = a
		b.sort()
		f = 0
		for j in range((n + 1) // 2):
			if b[j] == b[j + n // 2]:
				print('NO')
				f = 1
				break
		if f == 1:
			continue
		if n % 2 == 0 and b[0] == b[n // 2 - 1] and (b[n // 2] == b[n - 1]):
			print('NO')
			continue
		c = []
		c.extend(b[int(n / 2):])
		c.extend(b[:int(n / 2)])
		print('YES')
		print(*b)
		print(*c)
go()


from collections import defaultdict

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	cnt = defaultdict(int)
	for i in a:
		cnt[i] += 1
		if cnt[i] > n // 2:
			print('NO')
			return
	if n % 2 == 0 and (a[0] == a[n // 2 - 1] and a[n // 2] == a[n - 1]):
		print('NO')
	else:
		print(f"YES\n{' '.join(map(str, a))}\n{' '.join(map(str, a[n // 2:]))} {' '.join(map(str, a[:n // 2]))}")
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	x = list(set(arr))
	flag = True
	for i in x:
		if arr.count(i) > n // 2:
			flag = False
			break
	if flag == True:
		if len(x) == 2 and arr.count(x[0]) == arr.count(x[1]):
			print('NO')
		else:
			print('YES')
			print(*arr)
			x1 = n // 2
			print(*arr[x1:] + arr[:x1])
	else:
		print('NO')


def solution():
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	stat = 1
	for i in range((N + 1) // 2):
		if A[i] == A[i + N // 2]:
			print('NO')
			stat = 0
			return
	if stat and N % 2 == 0 and (A[0] == A[N // 2 - 1]) and (A[N // 2] == A[N - 1]):
		print('NO')
	else:
		print('YES')
		print(' '.join(map(str, A)))
		print(' '.join(map(str, A[(N + 1) // 2:])), end=' ')
		print(' '.join(map(str, A[:(N + 1) // 2])))
for _ in range(int(input())):
	solution()


from collections import Counter
test = int(input())
for _ in range(test):
	n = int(input())
	A = list(map(int, input().split()))
	c = Counter(A)
	m = max(c.values())
	if m > n // 2 or len(c) <= 2:
		print('NO')
	else:
		print('YES')
		A.sort()
		print(*A)
		p = n // 2
		print(*A[p:] + A[:p])


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in l:
		d[i] = d.get(i, 0) + 1
	mx = 0
	for i in d.values():
		if i >= mx:
			mx = i
	if len(d) == 2:
		print('NO')
	elif n % 2 == 0:
		if mx <= n // 2:
			print('YES')
			l.sort()
			for i in range(n):
				print(l[i], end=' ')
			print()
			for i in range(n // 2, n):
				print(l[i], end=' ')
			print(end='')
			for i in range(0, n // 2):
				print(l[i], end=' ')
			print()
		else:
			print('NO')
	elif mx < n // 2 + 1:
		print('YES')
		l.sort()
		for i in range(n):
			print(l[i], end=' ')
		print()
		for i in range(n // 2 + 1, n):
			print(l[i], end=' ')
		print(end='')
		for i in range(0, n // 2 + 1):
			print(l[i], end=' ')
		print()
	else:
		print('NO')


tc = int(input())
for t in range(0, tc):
	length = int(input())
	nums = list(map(int, input().split()))
	Map = {}
	for n in nums:
		Map[n] = Map.setdefault(n, 0) + 1
		if Map[n] > length // 2:
			print('NO')
			break
	else:
		if len(Map) == 2 and length % 2 == 0:
			print('NO')
		else:
			freqs = sorted(set(Map.values()), reverse=True)
			ans = []
			for freq in freqs:
				for (key, value) in Map.items():
					if value == freq:
						ans += [str(key)] * value
			print('YES')
			print(' '.join(ans))
			print(' '.join(ans[Map[int(ans[0])]:] + ans[:Map[int(ans[0])]]))


t = int(input())
for test in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	lst2 = lst[n // 2:] + lst[:n // 2]
	ans = 'YES'
	for i in range(n):
		if lst[i] == lst2[i]:
			ans = 'NO'
			break
	p1 = 1
	p2 = n - 2
	while p1 < p2:
		temp1 = sorted(lst[p1:p2 + 1])
		temp2 = sorted(lst2[p1:p2 + 1])
		if temp1 == temp2:
			ans = 'NO'
			break
		p1 += 1
		p2 -= 1
	print(ans)
	if ans == 'YES':
		print(*lst)
		print(*lst2)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(1, how_much_noob_I_am + 1):
		n = inpu()
		arr = lis()
		c = Counter(arr)
		p = sum(c.values())
		m = max(c.values())
		if p - m < m or (m == n // 2 and len(set(arr)) == 2):
			print('NO')
			continue
		arr.sort()
		res = arr[(len(arr) + 1) // 2:] + arr[:(len(arr) + 1) // 2]
		print('YES')
		print(*arr)
		print(*res)
main()


for _ in range(int(input())):
	n = int(input())
	l = input().split()
	d = {}
	for i in l:
		i = int(i)
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	l = []
	for i in d:
		l.append([i, d[i]])
	if len(l) == 1:
		print('NO')
	elif len(l) == 2:
		if l[0][0] == l[1][0] and (l[0][1] == 1 or l[0][1] == 2):
			print('YES')
			s = str(l[0][0]) * l[0][1] + str(l[1][0]) * l[0][1]
		else:
			print('NO')
	else:
		le = n // 2
		ma = l[0][1]
		s = []
		for i in l:
			s[len(s):] = [i[0]] * i[1]
			if i[1] > ma:
				ma = i[1]
		if ma > le:
			print('NO')
		else:
			print('YES')
			for i in s:
				print(i, end=' ')
			print()
			s = s[le:] + s[0:le]
			for i in s:
				print(i, end=' ')
			print()


import sys
import math
from collections import defaultdict, Counter, deque
from bisect import *
from string import ascii_lowercase
from heapq import *

def readInts():
	x = list(map(int, sys.stdin.readline().rstrip().split()))
	return x[0] if len(x) == 1 else x

def readList(type=int):
	x = sys.stdin.readline()
	x = list(map(type, x.rstrip('\n\r').split()))
	return x

def readStr():
	x = sys.stdin.readline().rstrip('\r\n')
	return x
write = sys.stdout.write
read = sys.stdin.readline

def dist(x1, x2, y1, y2):
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

def mergeSort(arr, check=lambda a, b: a < b, reverse=False):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, check, reverse)
		mergeSort(R, check, reverse)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if check(L[i], R[j]):
				if not reverse:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			elif not reverse:
				arr[k] = R[j]
				j += 1
			else:
				arr[k] = L[i]
				i += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

def maxSum(arr):
	max_sum = float('-inf')
	max_cur = 0
	for num in ar:
		max_cur = max(max_cur + num, num)
		if max_cur > max_sum:
			max_sum = max_cur
	return max_sum

def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, b % a)

def get_power(n, m):
	i = 1
	p = -1
	while i <= n:
		i = i * m
		p += 1
	return p

def fact(n):
	f = 1
	for i in range(2, n + 1):
		f *= i
	return f

def find_closest(num, ar):
	min_d = float('inf')
	for num2 in ar:
		d = abs(num2 - num)
		if d < min_d:
			min_d = d
	return min_d

def check_pal(n):
	s = str(n)
	j = len(s) - 1
	i = 0
	while j > i:
		if s[i] != s[j]:
			return False
		i += 1
		j -= 1
	return True

def solve(t):
	n = readInts()
	ar = readList()
	cnt = 0
	mx_ele = ar[0]
	if len(set(ar)) < 3:
		print('NO')
		return None
	for num in ar:
		if num == mx_ele:
			cnt += 1
		else:
			cnt -= 1
		if cnt == 0:
			mx_ele = num
			cnt = 1
	if cnt > 0:
		cnt = 0
		for num in ar:
			if num == mx_ele:
				cnt += 1
		if cnt > n // 2:
			print('NO')
			return None
	res = []
	ar.sort()
	res = ar[n // 2:] + ar[:n // 2]
	print('YES')
	print(*ar)
	print(*res)

def main():
	t = 1
	sys.setrecursionlimit(12000)
	t = readInts()
	for i in range(t):
		solve(i + 1)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = {}
	for i in range(n):
		if a[i] in count:
			count[a[i]] += 1
		else:
			count[a[i]] = 1
	if len(count.keys()) <= 2:
		print('NO')
	elif max(count.values()) > n // 2:
		print('NO')
	else:
		print('YES')
		pairs = list(count.items())
		pairs.sort(key=lambda x: x[1], reverse=True)
		array1 = []
		for pair in pairs:
			for j in range(pair[1]):
				array1.append(pair[0])
		array2 = []
		shift = pairs[0][1]
		for i in range(n - shift, n):
			array2.append(array1[i])
		for i in range(n - shift):
			array2.append(array1[i])
		print(*array1)
		print(*array2)


from collections import Counter
for tcase in range(int(input())):
	n = int(input())
	a = Counter(map(int, input().split())).most_common()
	b = []
	for (k, v) in a:
		b.extend([k] * v)
	ans = False
	i = 1
	while not ans and i * 2 < len(a):
		c = []
		for (k, v) in a[i:]:
			c.extend([k] * v)
		for (k, v) in a[:i]:
			c.extend([k] * v)
		ans = all((bi != ci for (bi, ci) in zip(b, c)))
		i += 1
	if ans:
		print('YES')
		print(' '.join(map(str, b)))
		print(' '.join(map(str, c)))
	else:
		print('NO')


def Print(arr):
	for ele in arr:
		print(ele, end=' ')
	print()
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ar = arr[n // 2:]
	for i in range(n // 2):
		ar.append(arr[i])
	ans = True
	for i in range(n):
		if arr[i] == ar[i]:
			ans = False
			break
	d = {}
	for ele in arr:
		d[ele] = d.get(ele, 0) + 1
	if len(d) == 2:
		tm = []
		for ele in d:
			tm.append(d[ele])
		if tm[0] == tm[1]:
			ans = False
	if ans:
		print('YES')
		Print(arr)
		Print(ar)
	else:
		print('NO')


for _ in range(int(input())):
	size = int(input())
	L = list(map(int, input().split()))
	L.sort()
	s = set(L)
	c = 0
	for i in s:
		if L.count(i) > size // 2:
			print('NO')
			c = 1
			break
	if c == 1:
		continue
	if len(s) == 2:
		print('NO')
		continue
	print('YES')
	print(*L)
	temp = L[(size + 1) // 2:] + L[:(size + 1) // 2]
	print(*temp)


from math import *
a = int(input())
for x in range(a):
	b = int(input())
	c = list(map(int, input().split()))
	h = {}
	for y in range(b):
		if h.get(c[y]) == None:
			h[c[y]] = 1
		else:
			h[c[y]] += 1
	o = b // 2
	l = 0
	for y in h:
		if h[y] > o:
			l = -1
			break
	if len(h) <= 2:
		print('NO')
	elif l == -1:
		print('NO')
	else:
		print('YES')
		c.sort()
		print(*c)
		j = c[o:] + c[:o]
		print(*j)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	dit = Counter(arr)
	f = max(dit.values())
	if f > n // 2 or len(dit) == 2:
		print('NO')
		continue
	new = arr[n // 2:] + arr[:n // 2]
	print('YES')
	print(*arr)
	print(*new)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	for i in a:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	if max(d.values()) > n // 2:
		print('NO')
		continue
	if len(d) == 2:
		print('NO')
		continue
	print('YES')
	c = []
	a.sort()
	c = a[n // 2:] + a[:n // 2]
	print(*a)
	print(*c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	flag = False
	mp = {}
	for i in arr:
		if i not in mp:
			mp[i] = 1
		else:
			mp[i] += 1
		if mp[i] > n // 2:
			flag = True
	if flag:
		print('NO')
		continue
	if len(mp) == 2:
		print('NO')
		continue
	arr.sort()
	maxxx = 0
	for k in mp:
		if mp[k] > maxxx:
			maxxx = mp[k]
	num = []
	num = arr
	k = maxxx
	num = num[::-1]
	xx = num[:k - 1:-1]
	yy = num[k - 1::-1]
	num = yy + xx
	print('YES')
	print(*arr)
	print(*num)


import math
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	d = {}
	for x in range(n):
		if a[x] in d:
			d[a[x]] = d[a[x]] + 1
		else:
			d[a[x]] = 1
		m = max(d[a[x]], m)
	if m > n / 2:
		print('NO')
	else:
		d = list(d.items())
		if len(d) <= 2:
			print('NO')
			t -= 1
			continue
		print('YES')
		d = sorted(d, key=lambda x: x[1], reverse=True)
		for x in d:
			for y in range(x[1]):
				print(x[0], end=' ')
		print()
		for x in range(1, len(d)):
			for y in range(d[x][1]):
				print(d[x][0], end=' ')
		for y in range(d[0][1]):
			print(d[0][0], end=' ')
		print()
	t -= 1


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lc = []
	l.sort()
	for i in set(l):
		lc.append(l.count(i))
	lc.sort(reverse=True)
	if lc[0] > n // 2:
		print('NO')
		continue
	if lc[0] + lc[1] == n:
		print('NO')
		continue
	e = lc[0]
	lans = []
	for j in range(n):
		lans.append(l[(j + e) % n])
	print('YES')
	for j in l:
		print(j, end=' ')
	print()
	for j in lans:
		print(j, end=' ')
	print()


from collections import Counter
tc = int(input())
for case in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	nb2 = n // 2
	mx = max(c.values())
	if mx > nb2 or len(set(a)) == 2:
		print('NO')
		continue
	else:
		print('YES')
		a.sort()
		print(*a, sep=' ')
		print(*a[mx:] + a[:mx], sep=' ')


import math
T = int(input())
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	flag = 'Yes'
	l.sort()
	a = 1
	m = 0
	for i in range(1, N):
		if l[i - 1] == l[i]:
			a += 1
		else:
			if m < a:
				m = a
			a = 1
	if m < a:
		m = a
	if m > N // 2:
		print('NO')
		continue
	k = m
	i = 0
	B = l[k:] + l[:k]
	if l[0] == B[-1] and l[-1] == B[0]:
		print('NO')
		continue
	print('YES')
	for i in l:
		print(i, end=' ')
	print()
	for i in B:
		print(i, end=' ')
	print()


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = Counter(arr)
	m = max(c.values())
	if m >= (n + 1) / 2 or len(set(arr)) <= 2:
		print('NO')
	else:
		for el in c:
			if c[el] == m:
				break
		a = [el] * m
		b = []
		for el in c:
			if el != a[0]:
				b += [el] * c[el]
		print('YES')
		print(*a + b)
		print(*b + a)


for cas in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if len(set(l)) == 1:
		print('NO')
		continue
	if len(set(l)) == 2 and n % 2 == 0:
		i = 0
		j = n - 1
		flag = 0
		while i < j:
			if l[i] == l[j]:
				flag = 1
				break
			i += 1
			j -= 1
		if not flag:
			print('NO')
			continue
	d = {}
	flag = 0
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	mx = 0
	for i in d:
		if d[i] > mx:
			mx = d[i]
	if mx > n // 2:
		print('NO')
		continue
	else:
		print('YES')
		print(*l)
		print(*l[mx:] + l[:mx])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	pre = 0
	xx = 0
	d = dict()
	flag = False
	c = 0
	for x in set(l):
		d[x] = l.count(x)
		if d[x] > pre:
			xx = x
			pre = d[x]
		if d[x] > n - d[x]:
			flag = True
			break
		if d[x] == n // 2 and n % 2 == 0:
			c += 1
		if c == 2:
			flag = True
			break
	if flag:
		print('NO')
	else:
		print('YES')
		index = l.index(xx)
		while index + 1 < n:
			if l[index + 1] == xx:
				index += 1
			else:
				break
		print(*l)
		l = l[n // 2:] + l[:n // 2]
		print(*l)


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	L = A[N // 2:]
	L.extend(A[:N // 2])
	f = False
	for i in range(N - 1):
		if A[i] == L[i]:
			f = True
			break
		if A[i] == L[i + 1] and A[i + 1] == L[i]:
			f = True
			break
	if A[N - 1] == L[N - 1]:
		f = True
	if f:
		print('NO')
	else:
		print('YES')
		print(*A)
		print(*L)


import sys
from math import sqrt, gcd, factorial, ceil, floor
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	n = I()
	a = L()
	a.sort()
	c = a[n // 2:] + a[:n // 2]
	if any((a[i] == c[i] for i in range(n))) or any((a[i] == c[i + 1] and a[i + 1] == c[i] for i in range(n - 1))):
		print('NO')
		continue
	print('YES')
	print(*a)
	print(*c)


T = int(input())
for ts in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	A.sort()
	C = A.copy()
	C = C[(N + 1) // 2:N] + C[:(N + 1) // 2]
	check = True
	for i in range(N):
		if A[i] == C[i]:
			check = False
			break
	if N % 2 == 0 and A[N // 2 - 1] == C[N // 2] and (A[N // 2] == C[N // 2 - 1]):
		check = False
	if check:
		print('YES')
		print(' '.join(map(str, A)))
		print(' '.join(map(str, C)))
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	line = input()
	a = list(map(int, line.split()))
	a.sort()
	counts = [[a[0], 1]]
	curr_value = a[0]
	for i in range(1, n):
		if a[i] == curr_value:
			counts[-1][1] += 1
		else:
			curr_value = a[i]
			counts.append([a[i], 1])
	counts.sort(key=lambda x: x[1], reverse=True)
	highest_count = counts[0][1]
	if highest_count > n / 2 or len(counts) == 2:
		print('NO')
	else:
		print('YES')
		for item in a:
			print(item, end=' ')
		print()
		for i in range(n):
			index = (i + highest_count) % n
			print(a[index], end=' ')
		print()


def fi():
	return int(input())

def li():
	return list(map(int, input().split()))
t = fi()
for i in range(t):
	n = fi()
	a = li()
	m = {}
	for e in a:
		if e not in m:
			m[e] = 1
		else:
			m[e] += 1
	pos = True
	firstrot = 0
	m = dict(sorted(m.items(), key=lambda x: x[1], reverse=True))
	for (key, value) in m.items():
		if value > n / 2 or (value == n / 2 and len(m.keys()) == 2):
			pos = False
		firstrot = value
		break
	if not pos:
		print('NO')
	else:
		print('YES')
		templist = []
		for (key, value) in m.items():
			for j in range(value):
				templist.append(key)
		print(*templist)
		templist = templist[firstrot:] + templist[:firstrot]
		print(*templist)