An array is called *interesting* if no subarray of length greater than 2 is non-increasing or non-decreasing.

Chef has an array A of length N. He wants to make the array interesting by rearranging the elements in any order. 

If there exist multiple such arrays, output any one.  
If no such array exists, print -1 instead.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N denoting the length of array A.
- The next line contains N space separated integers, A_{1}, A_{2}, \ldots, A_{N}

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

For each test case, output on a single line, any possible interesting array.
If no such array is possible, output -1.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3
2 2 2
4
2 6 5 2
5
5 5 2 4 2
----- Sample Output 1 ------ 
-1
6 2 5 2
5 2 4 2 5

----- explanation 1 ------ 
Test case $1$: There is no way of arranging the elements such that no subarray of length greater than $2$ is non-increasing or non-decreasing.

Test case $2$: A possible rearrangement of the elements is $[6, 2, 5, 2]$. Note that the subarrays of length greater than $2$ are $\{[6, 2, 5], [2, 5, 2], [6, 2, 5, 2]\}$. None of these subarrays are non-increasing or non-decreasing.

Test case $3$: A possible rearrangement of the elements is $[5, 2, 4, 2, 5]$. Note that the subarrays of length greater than $2$ are $\{[5, 2, 4], [2, 4, 2], [4, 2, 5], [5, 2, 4, 2], [2, 4, 2, 5], [5, 2, 4, 2, 5]\}$. None of these subarrays are non-increasing or non-decreasing.

Difficulty: HARD
Tags: Sorting

Constructive algorithms

Ad-hoc
Skill types: Sorting

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	greater = a[n // 2:]
	lesser = a[:n // 2]
	valid = []
	for i in range(n // 2):
		valid.append(greater[i])
		valid.append(lesser[i])
	if n % 2 == 1:
		valid.append(greater[-1])
	interest = True
	for i in range(1, n - 1):
		if not (valid[i - 1] < valid[i] > valid[i + 1] or valid[i - 1] > valid[i] < valid[i + 1]):
			interest = False
	if interest == True:
		print(*valid)
	else:
		print(-1)


import math
for ii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n <= 2:
		print(-1)
	elif n == 3:
		if len(set(a)) == 1:
			print(-1)
		elif len(set(a)) == 3:
			print(a[1], a[2], a[0])
		elif a[0] == a[1]:
			print(a[0], a[2], a[0])
		else:
			print(a[1], a[0], a[1])
	else:
		l = []
		for i in range(n // 2):
			l.append(a[n // 2 + i])
			l.append(a[i])
			if l[-1] == l[-2]:
				print(-1)
				break
		else:
			if n % 2 == 0:
				print(*l)
			else:
				l.append(a[-1])
				print(*l)


from collections import Counter, deque, defaultdict
import statistics
import math

def validate(ans):
	val = 'equal'
	for i in range(1, n):
		if ans[i] > ans[i - 1]:
			sign = 'greater'
			if val == sign:
				return -1
		elif ans[i] < ans[i - 1]:
			sign = 'lesser'
			if val == sign:
				return -1
		elif ans[i] == ans[i - 1]:
			return -1
		val = sign
	return 0

def solve(n, arr):
	arr.sort()
	beg = 0
	end = n - 1
	mid = (n - 1) // 2
	r = mid
	ans = []
	while mid >= 0 or end > r:
		ans.append(arr[mid])
		mid -= 1
		if end > r:
			ans.append(arr[end])
			end -= 1
	if validate(ans) == -1:
		return [-1]
	return ans
for test in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*solve(n, arr))


import math
for ii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n <= 2:
		print(-1)
	elif n == 3:
		if len(set(a)) == 1:
			print(-1)
		elif len(set(a)) == 3:
			print(a[1], a[2], a[0])
		elif a[0] == a[1]:
			print(a[0], a[2], a[0])
		else:
			print(a[1], a[0], a[1])
	else:
		b = list(set(a))
		b.sort()
		d = {}
		for i in b:
			d[i] = 0
		for i in a:
			d[i] += 1
		b1 = []
		for i in range(len(b)):
			b1.append(d[b[i]])
		x = max(b1)
		if x > math.ceil(n / 2):
			print(-1)
		elif x == math.ceil(n / 2):
			if n % 2 == 0:
				l = []
				for i in range(n // 2):
					l.append(a[n // 2 + i])
					l.append(a[i])
					if l[-1] == l[-2]:
						print(-1)
						break
				else:
					print(*l)
			elif a.count(b[0]) == x or a.count(b[-1]) == x:
				l = []
				for i in range(n // 2):
					l.append(a[n // 2 + i])
					l.append(a[i])
				l.append(a[-1])
				print(*l)
			else:
				print(-1)
		else:
			l = []
			for i in range(n // 2):
				l.append(a[n // 2 + i])
				l.append(a[i])
			if n % 2 == 0:
				print(*l)
			else:
				l.append(a[-1])
				print(*l)


def check(lst):
	for i in range(1, len(lst) - 1):
		if lst[i + 1] >= lst[i] >= lst[i - 1]:
			return False
		if lst[i + 1] <= lst[i] <= lst[i - 1]:
			return False
	return True
T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	if N == 1 or N == 2:
		print(*res)
		continue
	i = 0
	j = N // 2
	res = []
	while i < N // 2:
		res.append(arr[i])
		res.append(arr[j])
		i += 1
		j += 1
	if N % 2 == 1:
		res.append(arr[-1])
	i = 0
	j = N // 2
	res1 = []
	while i < N // 2:
		res1.append(arr[j])
		res1.append(arr[i])
		i += 1
		j += 1
	if N % 2 == 1:
		res1.append(arr[-1])
	if check(res):
		print(*res)
	elif check(res1):
		print(*res1)
	else:
		print(-1)


from collections import Counter
import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = Counter(l)
	flag = 1
	ans = []
	l.sort()
	if len(l) < 3:
		print(*l)
	else:
		for i in p:
			if p[i] > math.ceil(n / 2):
				print(-1)
				flag = 0
				break
		if flag == 1:
			if n % 2 == 0:
				for i in range(n // 2):
					ans.append(l[n // 2 + i])
					ans.append(l[i])
				print(*ans)
			else:
				for i in range(n // 2):
					ans.append(l[i])
					ans.append(l[n // 2 + i + 1])
				if ans[0] == l[n // 2]:
					ans.append(l[n // 2])
					print(*ans)
				else:
					r = [l[n // 2]]
					for i in ans:
						r.append(i)
					print(*r)


def maximum_subarray_with_same_value(arr):
	n = len(arr)
	max_len = 0
	i = 0
	while i < n:
		j = i + 1
		while j < n and arr[j] == arr[i]:
			j += 1
		max_len = max(max_len, j - i)
		i = j
	return max_len
t = int(input())
for _ in range(t):
	(n,) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	m = maximum_subarray_with_same_value(a)
	if m > n // 2:
		print(-1)
		continue
	ans = []
	(i, j) = (0, n // 2)
	while i < n // 2:
		ans.append(a[j])
		ans.append(a[i])
		i += 1
		j += 1
	if n % 2 != 0:
		ans.append(a[j])
	print(*ans)


def impossible(arr):
	for i in range(len(arr) - 2):
		if len(set(arr[i:i + 3])) == 1:
			return True
	return False
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort()
	a1 = arr[:len(arr) // 2]
	a2 = arr[len(arr) // 2:]
	sol = []
	for j in range(len(a2)):
		sol.append(a2[j])
		if len(a1) > j:
			sol.append(a1[j])
	if impossible(sol):
		print(-1)
	else:
		print(' '.join(list(map(str, sol))))


from collections import defaultdict
import math as mt

def check(b):
	n = len(b)
	for i in range(1, n - 1):
		if b[i - 1] > b[i] and b[i] < b[i + 1]:
			continue
		elif b[i - 1] < b[i] and b[i] > b[i + 1]:
			continue
		else:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n == 1 or n == 2:
		print(*a)
		continue
	a.sort()
	l1 = []
	l2 = []
	for i in range(n // 2):
		l1.extend([a[i], a[n // 2 + i]])
	for i in range(n // 2):
		l2.extend([a[n // 2 + i], a[i]])
	if n & 1:
		l1.append(a[-1])
		l2.append(a[-2])
	if check(l1):
		print(*l1)
	elif check(l2):
		print(*l2)
	else:
		print(-1)


def solve(a, d, f):
	a1 = a[0:d]
	a2 = a[d:]
	b = []
	d = min(len(a1), len(a2))
	if f == 0:
		for i in range(d):
			b.append(a2[i])
			b.append(a1[i])
		b.append(a2[-1])
	else:
		for i in range(d):
			b.append(a1[i])
			b.append(a2[i])
		b.append(a1[-1])
	return b

def check(b):
	for i in range(len(b) - 2):
		if b[i] <= b[i + 1] <= b[i + 2] or b[i] >= b[i + 1] >= b[i + 2]:
			return 0
	return 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n == 1:
		print(a[0])
	elif n == 2:
		print(a[0], a[1])
	elif n % 2 == 0:
		a1 = a[:n // 2]
		a2 = a[n // 2:]
		b = []
		for i in range(n // 2):
			b.append(a2[i])
			b.append(a1[i])
		if check(b):
			print(*b)
		else:
			print(-1)
	else:
		md1 = n // 2
		md2 = n // 2 + 1
		b1 = solve(a, md1, 0)
		b2 = solve(a, md2, 1)
		if check(b1):
			print(*b1)
		elif check(b2):
			print(*b2)
		else:
			print(-1)


from statistics import mode
a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	x = mode(A)
	y = A.count(x)
	t = 0
	if N >= 3:
		A.sort()
		if N % 2 == 0:
			if y > N // 2:
				t += 1
			else:
				arr = [0] * N
				for j in range(N):
					if j % 2 == 0:
						arr[j] = A[j // 2 + N // 2]
					else:
						arr[j] = A[(j - 1) // 2]
		elif y > N // 2 + 1:
			t += 1
		else:
			arr = [0] * N
			for j in range(N):
				if j % 2 == 0:
					arr[j] = A[j // 2 + (N - 1) // 2]
				else:
					arr[j] = A[(j - 1) // 2]
		if t >= 1:
			print(-1)
		else:
			for j in range(N):
				print(arr[j], end=' ')
			print('')
	else:
		for j in range(N):
			print(A[j], end=' ')
		print('')


from collections import Counter

def check(n, arr):
	i = 0
	while i < n:
		cur = arr[i]
		count = 0
		while i < n and arr[i] == cur:
			count += 1
			i += 1
		if count > 2:
			return False
	return True

def soln(n, arr):
	arr.sort()
	res = []
	left = arr[:n // 2]
	right = arr[n // 2:]
	res = []
	j = k = 0
	for i in range(n):
		if i & 1:
			res.append(left[j])
			j += 1
		else:
			res.append(right[k])
			k += 1
	if not check(n, res):
		return [-1]
	return res
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*soln(n, arr))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = [0] * n
	c = [0] * n
	for i in range(0, n, 2):
		b[i] = a[i // 2]
	for i in range(1, n, 2):
		b[i] = a[(n + i) // 2]
	for i in range(0, n, 2):
		c[i] = a[(n + i) // 2]
	for i in range(1, n, 2):
		c[i] = a[i // 2]
	ans = 0
	final = b
	for i in range(1, n - 1):
		if (b[i] - b[i - 1]) * (b[i] - b[i + 1]) <= 0:
			ans += 1
			final = c
			break
	for i in range(1, n - 1):
		if (c[i] - c[i - 1]) * (c[i] - c[i + 1]) <= 0:
			ans += 1
			final = b
			break
	if ans == 2:
		print(-1)
	else:
		for i in final:
			print(i, end=' ')
		print()


def solve(n, arr):
	if n <= 2:
		return arr
	arr_b = arr[:]
	arr_b.sort()
	arr_c = arr_b[:len(arr_b) // 2]
	arr_d = arr_b[len(arr_b) // 2:]
	arr_e = []
	i = 0
	j = 0
	while i < len(arr_c) and j < len(arr_d):
		arr_e.append(arr_d[j])
		arr_e.append(arr_c[i])
		i += 1
		j += 1
	if n % 2 == 1:
		arr_e.append(arr_d[-1])
	for j in range(10):
		for i in range(0, n - 2):
			if arr_e[i] <= arr_e[i + 1] <= arr_e[i + 2] or arr_e[i] >= arr_e[i + 1] >= arr_e[i + 2]:
				(arr_e[i + 1], arr_e[i + 2]) = (arr_e[i + 2], arr_e[i + 1])
	for i in range(0, n - 2):
		if arr_e[i] <= arr_e[i + 1] <= arr_e[i + 2] or arr_e[i] >= arr_e[i + 1] >= arr_e[i + 2]:
			return -1
	if arr_e == arr:
		return -1
	else:
		return arr_e
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = solve(n, arr)
	if ans == -1:
		print(-1)
	else:
		print(*ans)


def check(ans, n):
	inc = int(ans[0] < ans[1])
	i = 1
	while i < n:
		if ans[i] == ans[i - 1]:
			return False
		if int(ans[i] > ans[i - 1]) == inc:
			inc = int(ans[i] < ans[i - 1])
		else:
			return False
		i += 1
	return True
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print(*arr)
		continue
	arr.sort()
	ans = []
	i = 0
	j = int((n + 1) / 2)
	half = j
	while i < half:
		ans.append(arr[i])
		if j < n:
			ans.append(arr[j])
		i += 1
		j += 1
	if check(ans, n):
		print(*ans)
		continue
	ans = []
	i = 0
	j = int(n / 2)
	while j < n:
		ans.append(arr[j])
		if i < n / 2:
			ans.append(arr[i])
		i += 1
		j += 1
	if check(ans, n):
		print(*ans)
		continue
	print(-1)


def check(ar):
	n = len(ar)
	for i in range(n - 2):
		if ar[i] >= ar[i + 1] >= ar[i + 2]:
			return 0
		if ar[i] <= ar[i + 1] <= ar[i + 2]:
			return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(interesting, interesting1) = ([0] * n, [0] * n)
	(interesting[0::2], interesting[1::2]) = (a[:(n + 1) // 2], a[(n + 1) // 2:])
	(interesting1[0::2], interesting1[1::2]) = (a[n // 2:], a[:n // 2])
	if check(interesting):
		print(*interesting)
	elif check(interesting1):
		print(*interesting1)
	else:
		print(-1)


def check(ar):
	n = len(ar)
	for i in range(n - 2):
		if ar[i] >= ar[i + 1] >= ar[i + 2]:
			return 0
		if ar[i] <= ar[i + 1] <= ar[i + 2]:
			return 0
	return 1

def interesting_array(n, a):
	a.sort()
	(b, c) = ([0] * n, [0] * n)
	(b[::2], b[1::2]) = (a[:(n + 1) // 2], a[(n + 1) // 2:])
	(c[::2], c[1::2]) = (a[n // 2:], a[:n // 2])
	if check(b):
		print(*b)
	elif check(c):
		print(*c)
	else:
		print(-1)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	interesting_array(n, arr)


def check(ar):
	n = len(ar)
	for i in range(n - 2):
		if ar[i] >= ar[i + 1] >= ar[i + 2]:
			return 0
		if ar[i] <= ar[i + 1] <= ar[i + 2]:
			return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	(b, c) = ([0] * n, [0] * n)
	(b[0::2], b[1::2]) = (a[:(n + 1) // 2], a[(n + 1) // 2:])
	(c[0::2], c[1::2]) = (a[n // 2:], a[:n // 2])
	if check(b):
		print(*b)
	elif check(c):
		print(*c)
	else:
		print(-1)


from sys import stdin
input = stdin.readline

def interesting(A):
	for i in range(N - 2):
		if A[i] <= A[i + 1] <= A[i + 2] or A[i] >= A[i + 1] >= A[i + 2]:
			return False
	return True

def construct(A1, A2):
	B = []
	for i in range(max(len(A1), len(A2))):
		if i < len(A1):
			B.append(A1[i])
		if i < len(A2):
			B.append(A2[i])
	return B

def solve(N, A):
	if N <= 2:
		return A
	A = sorted(A)
	A1 = A[(N + 1) // 2:]
	A2 = A[:(N + 1) // 2]
	B = construct(A1, A2)
	if interesting(B):
		return B
	A1 = A[N // 2:]
	A2 = A[:N // 2]
	B = construct(A1, A2)
	if interesting(B):
		return B
	return [-1]
T = int(input().strip())
for problem in range(1, T + 1):
	N = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	print(*solve(N, A))


def N():
	return int(input())

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

def S():
	return input()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def factors(n: int) -> list:
	s = set()
	step = 2 if n % 2 else 1
	for i in range(1, n ** 0.5 + 1, step):
		if n % i == 0:
			s.add(i)
			s.add(n // i)
	return factors

def c(aa):
	f = False
	for i in range(1, n - 1):
		if aa[i - 1] < aa[i] and aa[i] > aa[i + 1] or (aa[i - 1] > aa[i] and aa[i] < aa[i + 1]):
			continue
		f = True
	return f

def sorts(nums):
	sortedList = sorted(nums)
	n = len(nums)
	if n % 2 == 1:
		small = sortedList[:1 + n // 2][::-1]
		large = sortedList[1 + n // 2:][::-1]
		for i in range(1, n, 2):
			nums[i] = large[i // 2]
		for i in range(0, n, 2):
			nums[i] = small[i // 2]
	else:
		small = sortedList[:n // 2][::-1]
		large = sortedList[n // 2:][::-1]
		for i in range(1, n, 2):
			nums[i] = large[i // 2]
		for i in range(0, n, 2):
			nums[i] = small[i // 2]
for _ in range(N()):
	n = N()
	if 'codechef' == 28226329:
		print('Tanmay')
	a = A()
	sorts(a)
	if c(a):
		print(-1)
		continue
	for i in a:
		print(i, end=' ')
	print()


def fun(l):
	x = len(l) // 2
	pos = len(l) // 2
	while x > 0:
		l.insert(pos, l.pop(0))
		x -= 1
		pos += 1
	for i in range(n - 2):
		if l[i] >= l[i + 1] and l[i + 1] >= l[i + 2] or (l[i] <= l[i + 1] and l[i + 1] <= l[i + 2]):
			return True
	return False
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if fun(l) == 0:
		for x in l:
			print(x, end=' ')
		print()
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr2 = arr.copy()
	arr.sort(reverse=True)
	mid = n // 2
	(arr[1::2], arr[0::2]) = (arr[:mid], arr[mid:])
	flag = False
	for i in range(n - 2):
		if arr[i] == arr[i + 1] or arr[i + 1] == arr[i + 2]:
			flag = True
			break
	if flag:
		print(-1)
	else:
		print(*arr)


t = int(input())
for _ in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if L[i] in d:
			d[L[i]] += 1
		else:
			d[L[i]] = 1
	M = []
	for i in d:
		M.append((i, d[i]))
	M.sort()
	if n == 1 or n == 2:
		print(*L)
		continue
	if len(M) == 1:
		print(-1)
		continue
	A = []
	(x, y) = M[0]
	i = 0
	f = True
	A.append(x)
	y -= 1
	for j in range(1, len(M)):
		(a, b) = M[j]
		for k in range(b):
			A.append(a)
			if y > 0:
				A.append(x)
				y -= 1
			elif A[i] < A[-1]:
				A.append(A[i])
				i += 1
			else:
				A.pop()
				x = a
				y = b - k
				break
	B = []
	if y == 1 and A[-1] != x:
		A.append(x)
		y -= 1
	if y > 0:
		print(-1)
		continue
	if not f:
		print(-1)
		continue
	for j in range(i, len(A)):
		B.append(A[j])
	print(*B)


def interesting(a):
	n = len(a)
	return n < 3 or all((a[i] < min(a[i - 1], a[i + 1]) or a[i] > max(a[i - 1], a[i + 1]) for i in range(1, n - 1)))
for tcase in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	(b, c) = ([], [])
	h = n // 2
	d = h + n % 2
	for i in range(h):
		b.append(a[i])
		b.append(a[i + d])
		c.append(a[i + h])
		c.append(a[i])
	if n % 2 == 1:
		b.append(a[h])
		c.append(a[-1])
	if interesting(b):
		print(' '.join(map(str, b)))
	elif interesting(c):
		print(' '.join(map(str, c)))
	else:
		print(-1)


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = [0] * n
	ans1 = [0] * n
	a.sort()
	i = 0
	j = n - 1
	for r in range(1, n, 2):
		ans[r] = a[i]
		ans1[r] = a[j]
		j -= 1
		i += 1
	for r in range(0, n, 2):
		ans[r] = a[i]
		ans1[r] = a[j]
		j -= 1
		i += 1
	p = 0
	q = 0
	for r in range(0, n - 2):
		k = sorted(ans[r:r + 3])
		if ans[r:r + 3] == k or ans[r:r + 3] == k[::-1]:
			p = 1
			break
	for r in range(0, n - 2):
		k = sorted(ans1[r:r + 3])
		if ans1[r:r + 3] == k or ans1[r:r + 3] == k[::-1]:
			q = 1
			break
	if p == 0:
		print(' '.join(map(str, ans)))
	elif q == 0:
		print(' '.join(map(str, ans1)))
	else:
		print(-1)


from collections import Counter
a = int(input())
for _ in range(a):
	c = int(input())
	b = list(map(int, input().split()))
	e = Counter(b)
	z = True
	f = False
	q = -100
	s = len(b)
	for i in e:
		if s % 2 == 0 and e[i] > len(b) // 2:
			z = False
			print(-1)
			break
		if s % 2 == 1 and e[i] == len(b) // 2 + 1 and (i == min(b) or i == max(b)):
			f = True
			q = i
			break
		if s % 2 == 1 and e[i] > len(b) // 2:
			z = False
			print(-1)
			break
	if z:
		b.sort()
		if f:
			if q == max(b):
				z = b[0:len(b) // 2]
				x = b[len(b) // 2:len(b)]
				for i in range(len(x) - 1):
					print(x[i], end=' ')
					print(z[i], end=' ')
				print(x[-1])
			else:
				z = b[0:len(b) // 2 + 1]
				x = b[len(b) // 2 + 1:len(b)]
				for i in range(len(z) - 1):
					print(z[i], end=' ')
					print(x[i], end=' ')
				print(z[-1])
		elif len(b) % 2 == 0:
			z = b[0:len(b) // 2]
			x = b[len(b) // 2:len(b)]
			for i in range(len(x)):
				print(x[i], end=' ')
				print(z[i], end=' ')
			print()
		else:
			z = b[0:len(b) // 2 + 1]
			x = b[len(b) // 2 + 1:len(b)]
			for i in range(len(z) - 1):
				print(z[i], end=' ')
				print(x[i], end=' ')
			print(z[-1])


t = int(input())
for t0 in range(t):
	n = int(input())
	a_i = list(map(int, input().split()))
	max_valid_count = int(n / 2) + 1
	num_count = {}
	for num in a_i:
		if not num_count.__contains__(num):
			num_count[num] = 0
		num_count[num] += 1
	max_occurred_item = max(num_count.items(), key=lambda item: item[1])
	if max_occurred_item[1] > max_valid_count:
		print(-1)
		continue
	a_i = sorted(a_i)
	middle_i = int(n / 2)
	list1 = a_i[:middle_i]
	list2 = a_i[middle_i:]
	result = []
	for i in range(len(list1)):
		result.append(list2[i])
		result.append(list1[i])
	if len(list1) != len(list2):
		result.append(list2[-1])
	print(' '.join([str(item) for item in result]))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	if n == 1:
		print(a[0])
	elif n == 2:
		print(a[0], a[1])
	else:
		new = [-1] * n
		ind = 1
		while ind < n:
			new[ind] = a.pop()
			ind += 2
		ind = 0
		while ind < n:
			new[ind] = a.pop()
			ind += 2
		flag = 0
		for i in range(n - 2):
			if new[i] <= new[i + 1] and new[i + 1] <= new[i + 2]:
				flag = 1
				break
			if new[i] >= new[i + 1] and new[i + 1] >= new[i + 2]:
				flag = 1
				break
		if flag == 1:
			print(-1)
		else:
			print(*new)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = []
	for i in range(0, n // 2):
		b += [a[n // 2 + i]]
		b += [a[i]]
	if n % 2 != 0:
		b += [a[-1]]
	f = 0
	for i in range(0, len(b) - 1):
		if b[i] == b[i + 1]:
			print(-1)
			f = 1
			break
	if f == 0:
		for i in range(len(b)):
			print(b[i], end=' ')
		print()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	l1 = []
	l2 = []
	l.sort(reverse=True)
	for i in range(0, n // 2):
		l1.append(l[i])
	l1.reverse()
	for i in range(n // 2, n):
		l2.append(l[i])
	l2.reverse()
	l.clear()
	for i in range(n):
		if i % 2 == 0:
			l.append(l2.pop())
		else:
			l.append(l1.pop())
	if n <= 2:
		print(*l)
	else:
		f = 0
		for i in range(1, n - 1):
			if l[i - 1] <= l[i] and l[i] <= l[i + 1] or (l[i - 1] >= l[i] and l[i] >= l[i + 1]):
				f = 1
				break
		if f == 1:
			print(-1)
		else:
			print(*l)


from copy import copy
from collections import deque

def check(arr):
	n = len(arr)
	for i in range(n - 2):
		if arr[i] <= arr[i + 1] <= arr[i + 2] or arr[i] >= arr[i + 1] >= arr[i + 2]:
			return False
	else:
		return True
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(a1, a2) = (a[:(n + 1) // 2], a[(n + 1) // 2:])
	if n <= 2:
		print(*a)
		continue
	b = []
	for i in range(n // 2):
		b.append(a1[i])
		b.append(a2[i])
	if len(a1) > len(a2):
		b.append(a1[-1])
	c = []
	for i in range(n // 2):
		c.append(a2[i])
		c.append(a1[i])
	if len(a1) > len(a2):
		c.append(a1[-1])
	if check(b):
		print(*b)
	elif check(c):
		print(*c)
	else:
		print(-1)