You are a game designer and want to make an obstacle course. The player will walk from left to right. You have $n$ heights of mountains already selected and want to arrange them so that the absolute difference of the heights of the first and last mountains is as small as possible.

In addition, you want to make the game difficult, and since walking uphill or flat is harder than walking downhill, the difficulty of the level will be the number of mountains $i$ ($1 \leq i < n$) such that $h_i \leq h_{i+1}$ where $h_i$ is the height of the $i$-th mountain. You don't want to waste any of the mountains you modelled, so you have to use all of them.

From all the arrangements that minimize $|h_1-h_n|$, find one that is the most difficult. If there are multiple orders that satisfy these requirements, you may find any.


-----Input-----

The first line will contain a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of mountains.

The second line of each test case contains $n$ integers $h_1,\ldots,h_n$ ($1 \leq h_i \leq 10^9$), where $h_i$ is the height of the $i$-th mountain.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output $n$ integers — the given heights in an order that maximizes the difficulty score among all orders that minimize $|h_1-h_n|$.

If there are multiple orders that satisfy these requirements, you may output any.


-----Examples-----

Input
2
4
4 2 1 2
2
3 1
Output
2 4 1 2 
1 3


-----Note-----

In the first test case:

The player begins at height $2$, next going up to height $4$ increasing the difficulty by $1$. After that he will go down to height $1$ and the difficulty doesn't change because he is going downhill. Finally the player will go up to height $2$ and the difficulty will increase by $1$. The absolute difference between the starting height and the end height is equal to $0$ and it's minimal. The difficulty is maximal.

In the second test case:

The player begins at height $1$, next going up to height $3$ increasing the difficulty by $1$. The absolute difference between the starting height and the end height is equal to $2$ and it's minimal as they are the only heights. The difficulty is maximal.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms

Implementation

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
list_ans = []
for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	i1 = 0
	a = 10 ** 9
	for i in range(n - 1):
		if a > list1[i + 1] - list1[i]:
			a = list1[i + 1] - list1[i]
			i1 = i
		if a == 0:
			break
	list_ans.append(' '.join(map(str, [list1[i1]] + list(list1[i1 + 2:]) + list(list1[:i1]) + [list1[i1 + 1]])))
for item in list_ans:
	print(item)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n == 2:
		print(a[0], a[1])
		continue
	max = 1 + 10 ** 9
	for i in range(1, n):
		if a[i] - a[i - 1] < max:
			max = a[i] - a[i - 1]
			x = i
		if max == 0:
			break
	print(' '.join(list(map(str, a[x:]))) + ' ' + ' '.join(list(map(str, a[:x]))))


from collections import Counter

def solution(arr):
	arr.sort()
	min_diff = float('inf')
	for i in range(len(arr) - 1):
		(num1, num2) = (arr[i], arr[i + 1])
		if num2 - num1 < min_diff:
			min_diff = num2 - num1
			idx = i
	return [arr[idx]] + arr[idx + 2:] + arr[:idx] + [arr[idx + 1]]
N = int(input())
for _ in range(N):
	input()
	arr = list(map(int, input().split()))
	print(' '.join(map(str, solution(arr))))


def sol(A):
	A = sorted(A)
	minn = 2 ** 31
	for i in range(len(A) - 1):
		if A[i + 1] - A[i] < minn:
			minn = A[i + 1] - A[i]
			(a, b, x) = (A[i], A[i + 1], i)
	ans = [a] + A[x + 2:] + A[:x] + [b]
	return ' '.join(map(str, ans))
x = int(input())
for _ in range(x):
	y = int(input())
	A = list(map(int, input().split()))
	print(sol(A))


ans = []
for _ in range(int(input())):
	n = int(input())
	u = list(map(int, input().split()))
	u.sort()
	ind = -1
	d = 10 ** 10
	for i in range(1, n):
		if u[i] - u[i - 1] < d:
			d = u[i] - u[i - 1]
			ind = i
	p = u[ind:] + u[:ind]
	(p[0], p[-1]) = (p[-1], p[0])
	ans.append(' '.join(map(str, p)))
print('\n'.join(ans))


test_cases = int(input())

def handle() -> str:
	n = int(input())
	values = sorted([int(i) for i in input().split(' ')])
	best_diff = float('inf')
	best_pair_indexes = None
	for i in range(len(values) - 1):
		if values[i + 1] - values[i] < best_diff:
			best_diff = values[i + 1] - values[i]
			best_pair_indexes = [i, i + 1]
	greater = values[best_pair_indexes[1] + 1:]
	smaller = values[:best_pair_indexes[0]]
	result = [values[best_pair_indexes[0]]] + greater + smaller + [values[best_pair_indexes[1]]]
	return ' '.join((str(s) for s in result))
for _ in range(test_cases):
	print(handle())


def solve(N, H):
	H.sort()
	mindiff = float('inf')
	mindiff_height_idx = None
	for i in range(len(H) - 1):
		diff = H[i + 1] - H[i]
		if diff < mindiff:
			mindiff = diff
			mindiff_height_idx = i
	(l, r) = (H[mindiff_height_idx], H[mindiff_height_idx + 1])
	res = [l]
	for i in range(mindiff_height_idx + 2, N):
		res.append(H[i])
	for i in range(mindiff_height_idx):
		res.append(H[i])
	res.append(r)
	return ' '.join(map(str, res))
T = int(input())
for t in range(T):
	N = int(input())
	H = list(map(int, input().split()))
	print(solve(N, H))


def solve():
	n = int(input())
	heights = [int(x) for x in input().split()]
	heights.sort()
	if n == 2:
		yield from heights
		return
	min_pair_index = 0
	for i in range(n - 1):
		if heights[i + 1] - heights[i] < heights[min_pair_index + 1] - heights[min_pair_index]:
			min_pair_index = i
	yield from heights[min_pair_index + 1:]
	yield from heights[:min_pair_index + 1]
for _ in range(int(input())):
	print(' '.join((str(x) for x in solve())))


import sys

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

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

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		arr.sort()
		minn = maxsize
		(i, j) = (0, 1)
		(indi, indj) = (0, 1)
		while j < n:
			if arr[j] - arr[i] < minn:
				minn = arr[j] - arr[i]
				indi = i
				indj = j
			i += 1
			j += 1
		res = [arr[indi]] + arr[indj + 1:] + arr[:indi] + [arr[indj]]
		get_print(' '.join(map(str, res)))
solve()


s = int(input())
for _ in range(s):
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	if len(a) <= 2:
		q = map(str, a)
		print(' '.join(q))
		continue
	(i, j) = (-1, -1)
	c = -1
	diff = 1000000007
	for k in range(1, len(a)):
		d = a[k] - a[k - 1]
		if diff > d:
			diff = d
			c = k
	q = map(str, a[c:] + a[:c])
	print(' '.join(q))


import math

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	minimal = a[1] - a[0]
	index = 0
	for i in range(n - 1):
		if a[i + 1] - a[i] <= minimal:
			index = i + 1
			minimal = a[i + 1] - a[i]
	if len(a) == 2:
		return ' '.join(map(str, a))
	ans = []
	for i in range(index, n):
		ans.append(str(a[i]))
	for i in range(index):
		ans.append(str(a[i]))
	return ' '.join(ans)
t = int(input())
while t > 0:
	t -= 1
	print(solve())


import math

def main_function():
	tests = range(int(input()))
	for test in tests:
		n = int(input())
		a = sorted([int(i) for i in input().split(' ')])
		prev = -1000000000000000
		difference = 10000000000000
		current_item = -1
		for i in range(len(a)):
			if a[i] - prev < difference:
				difference = a[i] - prev
				current_item = i
			prev = a[i]
		begin = a[current_item - 1]
		end = a[current_item]
		a.pop(current_item)
		a.pop(current_item - 1)
		bigger = []
		lower = []
		for i in a:
			if i <= begin:
				lower.append(i)
			else:
				bigger.append(i)
		a = [begin] + bigger + lower + [end]
		print(' '.join([str(i) for i in a]))
main_function()


q = int(input())
for t in range(q):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	if n == 2:
		print(' '.join(list(map(str, arr))))
	else:
		delta = 10 ** 10
		pos = -1
		for i in range(n - 1):
			if delta > arr[i + 1] - arr[i]:
				delta = arr[i + 1] - arr[i]
				pos = i
		arr = arr[pos + 1:] + arr[:pos + 1]
		print(' '.join(list(map(str, arr))))


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	data = list(map(int, input().split()))
	data.sort()
	minv = data[1] - data[0]
	minp = 0
	for i in range(n - 1):
		diff = data[i + 1] - data[i]
		if minv > diff:
			minv = diff
			minp = i
	li = data[minp:minp + 1] + data[minp + 2:] + data[0:minp] + data[minp + 1:minp + 2]
	print(' '.join(map(str, li)))


import math as m
for w in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	min_diff = arr[1] - arr[0]
	best_pos = 0
	for pos in range(1, n - 1):
		diff = arr[pos + 1] - arr[pos]
		if diff < min_diff:
			min_diff = diff
			best_pos = pos
	n = [arr[best_pos]]
	n += arr[best_pos + 2:]
	n += arr[:best_pos]
	n.append(arr[best_pos + 1])
	print(' '.join([str(x) for x in n]))


for iters in range(int(input())):
	n = int(input())
	array = [int(i) for i in input().split(' ')]
	array.sort()
	current = array[1] - array[0]
	j = 0
	for i in range(n - 1):
		a = array[i + 1] - array[i]
		if a <= current:
			current = a
			j = i
	a = array.pop(j)
	b = array.pop(j)
	semiout1 = ''
	if j < n - 2:
		semiout1 = ' '.join(map(str, array[j:])) + ' '
	semiout2 = ' '.join(map(str, array[0:j]))
	print(str(a) + ' ' + semiout1 + semiout2 + ' ' + str(b))


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	li = list(map(int, sys.stdin.readline().split()))
	li.sort()
	if n == 2:
		answer = li
	else:
		sub = li[1] - li[0]
		su = 0
		for i in range(1, len(li) - 1):
			if li[i + 1] - li[i] < sub:
				sub = li[i + 1] - li[i]
				su = i
		answer = [li[su]] + li[su + 2:] + li[:su] + [li[su + 1]]
	answer = list(map(str, answer))
	print(' '.join(answer))


t = int(input())
for _ in range(t):
	n = int(input())
	cliffs = list(map(int, input().split()))
	cliffs.sort()
	best = cliffs[1] - cliffs[0]
	start = 0
	for i in range(n - 1):
		diff = cliffs[i + 1] - cliffs[i]
		if diff < best:
			best = diff
			start = i
	if n == 2:
		l = cliffs
	else:
		l = cliffs[start + 1:] + cliffs[:start + 1]
	print(' '.join([str(x) for x in l]))


def I():
	return list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	nums = I()
	nums.sort()
	(li, hi) = (0, 0)
	mindiff = float('inf')
	for i in range(1, n):
		if nums[i] - nums[i - 1] < mindiff:
			(li, hi) = (i - 1, i)
			mindiff = nums[i] - nums[i - 1]
	res = [nums[li]] + nums[hi + 1:] + nums[:li] + [nums[hi]]
	res = [str(x) for x in res]
	print(' '.join(res))


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	H = [int(x) for x in input().split()]
	H = sorted(H)
	idx = 0
	mv = abs(H[0] - H[1])
	for i in range(N - 1):
		if H[i] == H[i + 1]:
			idx = i
			break
		elif abs(H[i] - H[i + 1]) < mv:
			idx = i
			mv = abs(H[i] - H[i + 1])
	H = [H[idx]] + H[idx + 2:] + H[:idx] + [H[idx + 1]]
	print(' '.join(map(str, H)))


def solve(ar):
	ar = sorted(ar)
	if len(ar) <= 2:
		return ar
	idx = 0
	for i in range(len(ar) - 1):
		if ar[i + 1] - ar[i] < ar[idx + 1] - ar[idx]:
			idx = i
	return [ar[idx]] + ar[idx + 2:] + ar[:idx] + [ar[idx + 1]]
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	ar = solve(ar)
	print(' '.join((str(v) for v in ar)))


for _ in range(int(input())):
	n = int(input())
	ms = list(map(int, input().split()))
	ms.sort()
	if len(ms) == 1:
		print(ms[0])
	elif len(ms) == 2:
		print(str(ms[0]) + ' ' + str(ms[-1]))
	else:
		index = n - 1
		min_ = ms[-1] - ms[-2]
		for i in range(n - 1, 0, -1):
			if ms[i] - ms[i - 1] <= min_:
				index = i
				min_ = ms[i] - ms[i - 1]
		(h1, hn) = (ms[index - 1], ms[index])
		ms = ms[0:index - 1] + ms[index + 1:]
		start = 0
		while start < n - 2 and ms[start] < h1:
			start += 1
		res = [h1] + ms[start:] + ms[:start] + [hn]
		print(' '.join([str(num) for num in res]))


for t in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	mn = 10 ** 10
	i = 1
	ind = 0
	if n > 2:
		while i < n:
			if h[i] - h[i - 1] < mn:
				mn = h[i] - h[i - 1]
				ind = i
			i += 1
		a = h[ind:] + h[:ind]
		print(' '.join(map(str, a)))
	else:
		print(' '.join(map(str, h)))


def solve(n, a):
	if n == 2:
		return ' '.join(map(str, a))
	k = a[-1] - a[0]
	x = 0
	for i in range(1, n):
		if a[i] - a[i - 1] <= k:
			k = a[i] - a[i - 1]
			x = i
	b = []
	c = []
	for i in range(n):
		if i < x:
			b.append(a[i])
		else:
			c.append(a[i])
	return ' '.join(map(str, c + b))
t = int(input())
for i in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	print(solve(n, a))


t = int(input())
for _ in range(t):
	n = int(input())
	h = [int(s) for s in input().split(' ')]
	h.sort()
	min_diff = float('inf')
	idx = -1
	for i in range(1, n):
		if h[i] - h[i - 1] < min_diff:
			min_diff = h[i] - h[i - 1]
			idx = i - 1
	(first, second) = (h[idx], h[idx + 1])
	h.pop(idx)
	h.pop(idx)
	h.insert(0, first)
	h.append(second)
	idx = -1
	for i in range(1, n - 1):
		if h[i] >= h[0]:
			idx = i
			break
	if idx == -1:
		print(' '.join(map(str, h)))
	else:
		ans = [h[0]]
		for i in range(idx, n - 1):
			ans.append(h[i])
		for i in range(1, idx):
			ans.append(h[i])
		ans.append(h[-1])
		print(' '.join(map(str, ans)))


def zigzag(a):
	a.sort()
	curr = (a[0], a[1], 0, 1)
	for i in range(1, len(a) - 1):
		if abs(curr[0] - curr[1]) > abs(a[i] - a[i + 1]):
			curr = (a[i], a[i + 1], i, i + 1)
	ans = [curr[0]]
	for j in range(curr[3] + 1, len(a)):
		ans.append(a[j])
	for k in range(0, curr[2]):
		ans.append(a[k])
	ans.append(curr[1])
	return ans

def main():
	for i in range(int(input())):
		int(input())
		ls = list(map(int, input().split()))
		print(' '.join(map(str, zigzag(ls))))
main()


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	l.sort()
	a = []
	for i in range(len(l) - 1):
		a.append(abs(l[i] - l[i + 1]))
	g = a.index(min(a))
	(x, y) = (l.pop(g), l.pop(g))
	k = [x]
	k = k + l[g:] + l[:g]
	k.append(y)
	print(' '.join((str(x) for x in k)))


def solve(arr):
	arr.sort()
	if len(arr) <= 2:
		return ' '.join([str(k) for k in arr])
	ind = 0
	for k in range(len(arr) - 1):
		if arr[k + 1] - arr[k] < arr[ind + 1] - arr[ind]:
			ind = k
	return ' '.join([str(k) for k in arr[ind + 1:] + arr[:ind + 1]])
cases = int(input())
for j in range(cases):
	length = int(input())
	arr = [int(k) for k in input().split()]
	print(solve(arr))


T = int(input())
for t in range(T):
	N = int(input())
	arr1 = [int(e) for e in input('').split()]
	arr1.sort()
	a = 0
	b = 1
	min1 = arr1[1] - arr1[0]
	for i in range(1, N):
		diff = arr1[i] - arr1[i - 1]
		if arr1[i] == arr1[i - 1]:
			a = i - 1
			b = i
			break
		if diff < min1:
			min1 = diff
			a = i - 1
			b = i
	arr2 = [arr1[a]]
	if b < len(arr1) - 1:
		for k in range(b + 1, len(arr1)):
			arr2.append(arr1[k])
	if a > 0:
		for k in range(0, a):
			arr2.append(arr1[k])
	arr2.append(arr1[b])
	print(' '.join([str(elem) for elem in arr2]))


for ii in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = []
	b = a + []
	b.sort()
	d = b[-1] - b[0]
	ix = 0
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] == 0:
			ix = i
			break
		if b[i + 1] - b[i] < d:
			d = b[i + 1] - b[i]
			ix = i
	m = b.pop(ix + 1)
	bgn = b[0:ix]
	b = b[ix:] + bgn + [m]
	print(' '.join([str(x) for x in b]))


def mountain(N, values):
	values = sorted(values)
	index = 0
	smallest = 2000000000.0
	for i in range(len(values) - 1):
		if values[i + 1] - values[i] < smallest:
			index = i
			smallest = values[i + 1] - values[i]
	l = values[index + 1:] + values[:index + 1]
	if len(l) == 2:
		l.reverse()
	print(' '.join([str(val) for val in l]))
for test_case in range(int(input())):
	N = int(input())
	val = [int(val) for val in input().split(' ')]
	mountain(N, val)


tests = int(input())
for _ in range(tests):
	l = int(input())
	test = list(map(int, input().split(' ')))
	test.sort()
	min_distance = 9999999999999999
	ind = 0
	if len(test) > 2:
		for i in range(l - 1):
			if test[i + 1] - test[i] < min_distance:
				min_distance = test[i + 1] - test[i]
				ind = i + 1
	str_test = list(map(str, test))
	print(' '.join(str_test[ind:]) + ' ' + ' '.join(str_test[:ind]))


t = int(input())
for i in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	if n == 2:
		print(' '.join(map(str, h)))
		continue
	pos = -1
	mn = 10 ** 9
	for i in range(1, n):
		if mn > abs(h[i] - h[i - 1]):
			pos = i
			mn = abs(h[i] - h[i - 1])
	result = []
	for i in range(pos, n):
		result.append(h[i])
	for i in range(pos):
		result.append(h[i])
	print(' '.join(map(str, result)))


for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()))
	b = [y - x for (x, y) in zip(a, a[1:])]
	i = b.index(min(b)) + (len(b) > 1)
	print(*a[i:] + a[:i])


t = int(input())
for _ in range(t):
	n = int(input())
	(*h,) = map(int, input().split())
	h.sort()
	if n == 2:
		print(h[0], h[1])
	else:
		pos = 0
		d = 10 ** 10
		for i in range(1, n):
			if h[i] - h[i - 1] < d:
				d = h[i] - h[i - 1]
				pos = i
		print(*h[pos:], *h[:pos])


def main():
	for t in range(int(input())):
		n = int(input())
		h = list(map(int, input().split()))
		h.sort()
		if n == 2:
			print(*h)
		elif h[0] == h[-1]:
			print(*h)
		else:
			(mindelta, index) = (1000000000, 0)
			for i in range(n - 1):
				if mindelta > h[i + 1] - h[i]:
					mindelta = h[i + 1] - h[i]
					index = i
			print(*h[index + 1:] + h[:index + 1])
main()


import sys
t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	global_dif = float('inf')
	for i in range(1, n):
		cur_dif = a[i] - a[i - 1]
		if global_dif > cur_dif:
			pos = i
			global_dif = cur_dif
		elif global_dif == cur_dif and i == n - 1:
			pos = i
			global_dif = cur_dif
	if pos == 1 or pos == n - 1:
		b = []
		b.append(a[pos - 1])
		for i in range(n):
			if i != pos and i != pos - 1:
				b.append(a[i])
		b.append(a[pos])
		print(' '.join(list(map(str, b))))
	else:
		b = []
		for i in range(pos, n):
			b.append(a[i])
		for i in range(pos):
			b.append(a[i])
		print(' '.join(list(map(str, b))))
	t -= 1


def main():
	for _ in range(int(input())):
		n = int(input())
		array = list(map(int, input().split()))
		array.sort()
		mini = float('inf')
		idx = -1
		for i in range(1, n):
			if array[i] - array[i - 1] < mini:
				mini = array[i] - array[i - 1]
				idx = i
		hills = array[idx:] + array[:idx]
		(hills[0], hills[-1]) = (hills[-1], hills[0])
		print(*hills)
main()


from math import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
from re import search
li = lambda : list(map(int, input().split()))
arr = lambda a: array('i', a)
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
sbstr = lambda a, s: search('.*'.join(a), s)

def solve():
	for _ in range(int(input())):
		n = int(input())
		h = sorted(li())
		if n == 2:
			print(*h)
			continue
		m = [10000000000.0, 0]
		for i in range(n - 1):
			if h[i + 1] - h[i] < m[0]:
				m = [h[i + 1] - h[i], i]
		print(*h[m[1] + 1:] + h[:m[1] + 1])
solve()


for _ in range(int(input())):
	n = int(input())
	h = sorted(map(int, input().split()))
	i = min(range(n - 1), key=lambda i: abs(h[i + 1] - h[i]))
	print(h[i], *h[i + 2:], *h[:i], h[i + 1])


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	c = []
	for i in range(n - 1):
		c.append(a[i + 1] - a[i])
	x = c.index(min(c))
	if len(c) == 1:
		print(*a)
	else:
		a1 = a[x + 1:] + a[:x + 1]
		print(*a1)
for _ in range(int(input())):
	solve()


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	data = list(map(int, sys.stdin.readline().split()))
	data.sort()
	if len(data) == 2:
		print(*data)
		continue
	idx = -1
	diff = 999999999
	for i in range(1, len(data)):
		if data[i] - data[i - 1] < diff:
			idx = i
			diff = data[i] - data[i - 1]
	print(*data[idx:], *data[:idx])


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	if n == 1:
		print(lst[0])
	lst.sort()
	(a, m) = (0, lst[1] - lst[0])
	for i in range(1, n - 1):
		if lst[i + 1] - lst[i] < m:
			m = lst[i + 1] - lst[i]
			a = i
	print(lst[a], *lst[a + 2:], *lst[:a], lst[a + 1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	if n < 3:
		print(*a)
		continue
	mn = a[1] - a[0]
	index = 1
	for i in range(1, n - 1):
		if a[i + 1] - a[i] < mn:
			mn = a[i + 1] - a[i]
			index = i + 1
	c = a[index:] + a[:index]
	print(*c)


for _ in range(int(input())):
	n = int(input())
	(*a,) = list(map(int, input().split()))
	a.sort()
	if n == 2:
		print(*a)
	else:
		x = 0
		d = 10 ** 10
		for i in range(1, n):
			if a[i] - a[i - 1] < d:
				d = a[i] - a[i - 1]
				x = i
		print(*a[x:], *a[:x])


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	pairs = [0, 1]
	diff = float('inf')
	for i in range(n - 1):
		if h[i + 1] - h[i] < diff:
			diff = h[i + 1] - h[i]
			pairs = [i, i + 1]
	(a, b) = pairs
	return [h[a]] + h[b + 1:] + h[:a] + [h[b]]
for _ in range(int(input())):
	print(*solve())


for t in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	m = 10 ** 11
	ind = 0
	for i in range(n - 1):
		if l[i + 1] - l[i] < m:
			m = l[i + 1] - l[i]
			ind = i
	if n == 2:
		print(*l)
	else:
		print(*l[ind + 1:] + l[:ind + 1])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	start = arr[0]
	start_i = 0
	end = arr[1]
	end_i = 1
	for i in range(1, len(arr) - 1):
		if arr[i + 1] - arr[i] < end - start:
			start = arr[i]
			end = arr[i + 1]
			start_i = i
			end_i = i + 1
	init_i = start_i
	last_i = end_i
	start_i = 0
	end_i = last_i + 1
	res = [start]
	while end_i < len(arr):
		res += [arr[end_i]]
		end_i += 1
	while start_i < init_i:
		res += [arr[start_i]]
		start_i += 1
	res += [arr[last_i]]
	print(' '.join(map(str, res)))


for i in range(int(input())):
	k = int(input())
	lst = sorted([int(x) for x in input().split()])
	if len(lst) < 3:
		print(*lst)
	else:
		s = lst[1] - lst[0]
		x = lst[0]
		y = lst[1]
		j = 0
		for i in range(1, len(lst) - 1):
			if lst[i + 1] - lst[i] < s:
				s = lst[i + 1] - lst[i]
				x = lst[i]
				y = lst[i + 1]
				j = i
			if s == 0:
				break
		lst3 = lst[j + 2:] + lst[:j]
		lst1 = [x] + lst3
		lst1.append(y)
		print(*lst1)


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	h.sort()
	if n == 2:
		print(*h)
	else:
		diffs = [abs(i - j) for (i, j) in zip(h, h[1:])]
		min_diff = min(diffs)
		min_i = diffs.index(min_diff)
		print(*h[min_i + 1:] + h[:min_i + 1])


import sys
t = int(input())
while t > 0:
	n = int(input())
	a = sorted(map(int, input().split()))
	if n == 2:
		print(str(a[0]) + ' ' + str(a[1]))
	else:
		i = 0
		d1 = min(range(n - 1), key=lambda k: a[k + 1] - a[k])
		print(a[d1], *a[d1 + 2:], *a[:d1], a[d1 + 1])
	t -= 1


import sys

def solve(heights):
	new_heights = []
	heights.sort()
	n = len(heights)
	smallest_diff = float('inf')
	best_index = -1
	for i in range(n - 1):
		if heights[i + 1] - heights[i] < smallest_diff:
			smallest_diff = heights[i + 1] - heights[i]
			best_index = i
	new_heights = [heights[best_index]] + heights[best_index + 2:] + heights[:best_index] + [heights[best_index + 1]]
	ans = ''
	for h in new_heights:
		ans += str(h) + ' '
	return ans[:-1]
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	line = sys.stdin.readline().strip()
	line = line.split(' ')
	line = map(lambda s: int(s), line)
	sys.stdout.write(solve(list(line)))
	sys.stdout.write('\n')


for test_case in range(int(input())):
	mountains = int(input())
	mountains_heights = sorted(list(map(int, input().split())))
	repeated = []
	differences = []
	counter = 0
	while counter < len(mountains_heights) - 1:
		differences.append(abs(mountains_heights[counter] - mountains_heights[counter + 1]))
		counter += 1
	differences.reverse()
	index = differences.index(min(differences))
	index = len(differences) - 1 - index
	result = mountains_heights[index + 1:] + mountains_heights[:index + 1]
	if len(result) == 2:
		result = sorted(result)
	print(' '.join(map(str, result)))


def define_min_diff_indeces(array, length):
	current_diff = abs(array[0] - array[1])
	indeces = [0, 1]
	for i in range(0, length - 1):
		diff = abs(array[i] - array[i + 1])
		if diff < current_diff:
			current_diff = diff
			indeces = [i, i + 1]
	if array[indeces[0]] > array[indeces[1]]:
		indeces.reverse()
	return indeces

def define_order(array, length):
	array.sort()
	(i1, i2) = define_min_diff_indeces(array, length)
	(part1, part2) = ([], [])
	for i in range(length):
		if i not in [i1, i2]:
			if array[i] > array[i2]:
				part1.append(array[i])
			else:
				part2.append(array[i])
	return [array[i1]] + part1 + part2 + [array[i2]]
result = []
quantity_tests = int(input())
for test in range(quantity_tests):
	length = int(input())
	array = list(map(int, input().split()))
	result.append(' '.join(map(str, define_order(array, length))))
print('\n'.join(result))


def main():
	t = int(input())
	for i in range(t):
		solve()

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	minD = a[-1] - a[0]
	minI = n - 1
	for i in range(1, n):
		if a[i] - a[i - 1] < minD:
			minI = i
			minD = a[i] - a[i - 1]
		if minD == 0:
			break
	last = a.pop(minI)
	first = a.pop(minI - 1)
	ans = [first] + a[minI - 1:] + a[:minI - 1] + [last]
	for i in ans:
		print(i, end=' ')
	print()
main()


def sol(n, l):
	l.sort()
	idx = 0
	d = float('inf')
	for i in range(n - 1):
		dis = l[i + 1] - l[i]
		if d > dis:
			d = dis
			idx = i
	st = l[idx]
	ed = l[idx + 1]
	ans = l[idx + 2:]
	ans.extend(l[:idx])
	ans.insert(0, st)
	ans.append(ed)
	print(*ans)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	sol(n, l)


def solve(A, n):
	A.sort()
	index = -1
	ldiff = float('inf')
	for i in range(n - 1):
		di = A[i + 1] - A[i]
		if di < ldiff:
			ldiff = di
			index = i + 1
	if n > 2:
		A = A[index:] + A[:index]
	print(*A)
for case in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	ans = solve(li, n)


import math
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	x = sorted([int(_) for _ in input().split()])
	d = 10 ** 10
	rec = -1
	for i in range(1, n):
		if x[i] - x[i - 1] < d:
			d = x[i] - x[i - 1]
			rec = i
	print(x[rec - 1], *x[rec + 1:], *x[:rec - 1], x[rec])
tt = int(input())
for test in range(tt):
	solve()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(N, a) = (int(input()), sorted(list(map(int, input().split()))))
	md = min(list(range(N - 1)), key=lambda i: a[i + 1] - a[i])
	d = a.pop(md + 1)
	print(*a[md:], *a[:md], d)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	diff = INF
	for i in range(n - 1):
		if A[i + 1] == A[i]:
			flag = 1
			corners = [i, i + 1]
			break
		k = abs(A[i] - A[i + 1])
		if k < diff:
			diff = k
			corners = [i, i + 1]
	k = corners[1]
	ans = []
	for i in range(k + 1, n):
		ans.append(A[i])
	for i in range(k - 1):
		ans.append(A[i])
	ans = [A[k - 1]] + ans + [A[k]]
	print(*ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


def main():
	tc = int(input())
	for zzz in range(tc):
		solve()

def solve():
	n = int(input())
	arr = [int(_) for _ in input().split()]
	arr.sort()
	a = 0
	import sys
	diff = sys.maxsize
	if n != 2:
		for i in range(1, n):
			if arr[i] - arr[i - 1] < diff:
				diff = arr[i] - arr[i - 1]
				a = i
	for i in range(a, n):
		print(arr[i], end=' ')
	for i in range(0, a):
		print(arr[i], end=' ')
	print()
main()


for t in range(int(input())):
	n = int(input())
	h = sorted(list(map(int, input().split())))
	mn = abs(h[0] - h[1])
	ind = 0
	for i in range(1, n - 1):
		if abs(h[i] - h[i + 1]) < mn:
			mn = abs(h[i] - h[i + 1])
			ind = i
	fir = h[ind]
	sec = h[ind + 1]
	print(fir, *h[ind + 2:], *h[:ind], sec)


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	if n == 2:
		print(a[0], a[1])
		return
	mink = a[1] - a[0]
	k = 1
	for i in range(1, n):
		if a[i] - a[i - 1] < mink:
			mink = a[i] - a[i - 1]
			k = i
	for i in range(k, n):
		print(a[i], end=' ')
	for i in range(k):
		print(a[i], end=' ')
	print()
t = int(input())
for _ in range(t):
	solve()


for _ in ' ' * int(input()):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	j = 0
	if n == 2:
		print(*x)
		continue
	m = 1000000000
	for i in range(n - 1):
		if abs(x[i] - x[i + 1]) < m:
			j = i
			m = abs(x[i] - x[i + 1])
	print(*x[j + 1:] + x[:j + 1])


for i in range(int(input())):
	len1 = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	ind = 0
	min1 = float('inf')
	for i in range(1, len1):
		t = list1[i] - list1[i - 1]
		if t < min1:
			min1 = t
			ind = i
	res = [list1[ind - 1]] + list1[ind + 1:] + list1[:ind - 1] + [list1[ind]]
	print(*res)


from math import *

def sol(n, arr):
	arr.sort()
	if n == 2:
		return arr
	x = inf
	y = -1
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			return arr[i:] + arr[:i]
		elif arr[i] - arr[i - 1] < x:
			x = arr[i] - arr[i - 1]
			y = i
	return arr[y:] + arr[:y]
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*sol(n, arr))


t = int(input())
for _ in range(t):
	input()
	a = list(map(int, input().split()))
	a = sorted(a)
	best_diff = a[1] - a[0]
	best_idx = 1
	for i in range(1, len(a)):
		if a[i] - a[i - 1] <= best_diff:
			best_diff = a[i] - a[i - 1]
			best_idx = i
	ans = [a[best_idx - 1]]
	used_idxs = set([best_idx - 1, best_idx])
	for i in range(best_idx + 1, len(a)):
		if a[i] != ans[-1]:
			ans.append(a[i])
			used_idxs.add(i)
	b = []
	d = {}
	for i in range(len(a)):
		if i not in used_idxs:
			ans.append(a[i])
	ans = ans + [a[best_idx]]
	print(' '.join(map(str, ans)))


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	pos = -1
	if n == 2:
		print(*nums)
	else:
		mn = float('inf')
		for i in range(1, n):
			if mn > abs(nums[i] - nums[i - 1]):
				mn = abs(nums[i] - nums[i - 1])
				pos = i
		nums = nums[pos:] + nums[:pos]
		print(*nums)


for s in [*open(0)][2::2]:
	i = j = 0
	d = 1000000000.0
	for (x, y) in zip((a := sorted(map(int, s.split()))), a[1 + (len(a) < 3):]):
		j += 1
		if y - x < d:
			d = y - x
			i = j
	print(*a[i:] + a[:i])


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	i = min(range(n - 1), key=lambda k: a[k + 1] - a[k])
	print(a[i], *a[i + 2:], *a[:i], a[i + 1])


import sys
t = int(sys.stdin.readline())
while t > 0:
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	a.sort()
	if n == 2:
		x = a
	else:
		mi = 1
		md = a[1] - a[0]
		for i in range(1, n - 1):
			d = a[i + 1] - a[i]
			if d < md:
				mi = i + 1
				md = d
		x = a[mi:] + a[:mi]
	print(*x)
	t -= 1


def solve(n, h):
	h.sort()
	diff = 1000000000000.0
	edges = []
	for i in range(1, n):
		if h[i] - h[i - 1] < diff:
			diff = h[i] - h[i - 1]
			edges = [i - 1, i]
	ans = []
	for i in range(edges[0], n):
		if i != edges[1]:
			ans.append(h[i])
	for i in range(0, edges[1] + 1):
		if i != edges[0]:
			ans.append(h[i])
	return ans
for t in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(*solve(n, h))


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	newarr = arr[2:]
	newarr.sort()
	fin = []
	mindiff = 10000000000
	cx = 0
	cy = 0
	for i in range(n - 1):
		diff = abs(arr[i + 1] - arr[i])
		if diff == 0:
			cx = i
			cy = i + 1
			break
		elif diff < mindiff:
			mindiff = diff
			cx = i
			cy = i + 1
	fin += [arr[cx]]
	if cy != n - 1:
		fin += arr[cy + 1:]
	fin += arr[:cx]
	fin += [arr[cy]]
	for ff in fin:
		print(ff, end=' ')
	print()


t = int(input())
for q in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	if n == 2:
		print(*arr)
		continue
	ind = None
	min = float('inf')
	for i in range(n - 1):
		if arr[i + 1] - arr[i] <= min:
			min = arr[i + 1] - arr[i]
			ind = i
			if min == 0:
				break
	print(*arr[ind + 1:], *arr[:ind + 1])


def ans():
	n = int(input())
	h = sorted(list(map(int, input().split())))
	mn = abs(h[0] - h[1])
	ind = 0
	for i in range(1, n - 1):
		if abs(h[i] - h[i + 1]) < mn:
			mn = abs(h[i] - h[i + 1])
			ind = i
	print(h[ind], *h[ind + 2:], *h[:ind], h[ind + 1])
for t in range(int(input())):
	ans()


for i in range(int(input())):
	k = int(input())
	lst = sorted([int(x) for x in input().split()])
	if len(lst) < 3:
		print(*lst)
	else:
		s = lst[1] - lst[0]
		j = 0
		for i in range(1, len(lst) - 1):
			if lst[i + 1] - lst[i] < s:
				s = lst[i + 1] - lst[i]
				j = i
			if s == 0:
				break
		print(lst[j], *lst[j + 2:], *lst[:j], lst[j + 1])


def solve(A, n):
	A.sort()
	diff = float('inf')
	index = -1
	for i in range(n - 1):
		cd = A[i + 1] - A[i]
		if cd < diff:
			diff = cd
			index = i + 1
	if n == 2:
		print(*A)
	else:
		A = A[index:] + A[:index]
		print(*A)
for caser in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	solve(A, n)


def cliffs(n, heights):
	heights.sort()
	min_distance = float('inf')
	min_dist_index = -1
	for i in range(n - 1):
		if heights[i + 1] - heights[i] < min_distance:
			min_distance = heights[i + 1] - heights[i]
			min_dist_index = i
	print(heights[min_dist_index], end=' ')
	for i in range(min_dist_index + 2, n):
		print(heights[i], end=' ')
	for i in range(min_dist_index):
		print(heights[i], end=' ')
	print(heights[min_dist_index + 1], end=' ')
	print()
for _ in range(int(input())):
	n = int(input())
	heights = list(map(int, input().split()))
	cliffs(n, heights)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ID = 1
	for i in range(1, n):
		if a[i] - a[i - 1] < a[ID] - a[ID - 1]:
			ID = i
	ans = [0] * n
	ans[0] = a[ID - 1]
	ans[-1] = a[ID]
	for i in range(ID + 1, n):
		ans[i - ID] = a[i]
	for i in range(ID - 1):
		ans[n - ID + i] = a[i]
	print(*ans)
for i in range(int(input())):
	solve()