Read problems statements in Mandarin Chinese and Russian as well. 

------ Problem description ------ 

You will be given a zero-indexed array A. You need to rearrange its elements in such a way that the following conditions are satisfied:

A[i] ≤ A[i+1] if i is even.
A[i] ≥ A[i+1] if i is odd.
In other words the following inequality should hold: A[0] ≤ A[1] ≥ A[2] ≤ A[3] ≥ A[4], and so on. Operations ≤ and ≥ should alter.

------ Input ------ 

The first line contains a single integer T denoting the number of test cases. The first line of each test case contains an integer N, that is the size of the array A. The second line of each test case contains the elements of array A

------ Output ------ 

For each test case, output a single line containing N space separated integers, which are the elements of A arranged in the required order. If there are more than one valid arrangements, you can output any of them.

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

$1 ≤ N ≤ 100000$
$Sum of N in one test file ≤ 600000$
$1 ≤ A[i] ≤ 10^{9}$

----- Sample Input 1 ------ 
2
2
3 2
3
10 5 2
----- Sample Output 1 ------ 
2 3
2 10 5
----- explanation 1 ------ 
Example case 1.A[0] ? A[1] is satisfied, 2 ? 3.Example case 2.A[0] ? A[1] is satisfied, 2 ? 10.A[1] ? A[2] is satisfied, 10 ? 5.Note: 5 10 2 is also valid answer.

Source: codechef | Difficulty: EASY
Tags: Sorting

Ad-hoc


Solutions:
t = int(input())
for tc in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	for j in range(1, n - 1, 2):
		(a[j], a[j + 1]) = (a[j + 1], a[j])
	print(*a)


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


t = int(input())
while t > 0:
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	new = []
	o = int(n / 2)
	if n == 1:
		new.append(x[0])
	elif n % 2 == 0:
		i = 0
		j = o
		k = 0
		while k < n:
			if k % 2 == 0:
				new.append(x[i])
				i = i + 1
			else:
				new.append(x[j])
				j = j + 1
			k = k + 1
	else:
		i = 0
		j = o + 1
		k = 0
		while k < n:
			if k % 2 == 0:
				new.append(x[i])
				i = i + 1
			else:
				new.append(x[j])
				j = j + 1
			k = k + 1
	print(' '.join([str(x) for x in new]))
	t = t - 1


for _ in range(int(input())):
	i = int(input())
	l = list(map(int, input().split()))
	l.sort()
	for j in range(1, i + 1, 2):
		if j < len(l) - 1:
			(l[j], l[j + 1]) = (l[j + 1], l[j])
		else:
			break
	for j in l:
		print(j, end=' ')
	print()


def rearrange_array(n, arr):
	arr.sort()
	for i in range(1, n - 1, 2):
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return arr
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(*rearrange_array(n, arr))


import math
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	B = [0] * n
	for j in range(0, math.ceil(n / 2)):
		B[2 * j] = A[j]
	c = 0
	for k in range(math.ceil(n / 2), n):
		B[2 * c + 1] = A[k]
		c += 1
	for l in B:
		print(l, end=' ')
	print()


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	print(a[0], end=' ')
	a = a[1:]
	i = 0
	while i < n // 2 - 1:
		print(a[2 * i + 1], a[2 * i], sep=' ', end=' ')
		i += 1
	if n % 2 == 0:
		print(a[-1])
	else:
		print(a[-1], a[-2], sep=' ')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(0, n - 1):
		if i % 2 == 0:
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		if i % 2 != 0:
			if a[i] < a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
	for k in a:
		print(k, end=' ')
	print()


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1):
		if i % 2 == 1:
			if a[i] <= a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		elif a[i] >= a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(*a)


for i in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	for i in range(1, n - 1, 2):
		(l[i], l[i + 1]) = (l[i + 1], l[i])
	print(*l)


for j in range(int(input())):
	x = int(input())
	n = input().split()
	for i in range(x - 1):
		a = int(n[i])
		b = int(n[i + 1])
		if i % 2 == 0:
			if a > b:
				temp = b
				b = a
				a = temp
		elif a < b:
			temp = b
			b = a
			a = temp
		n[i] = a
		n[i + 1] = b
	for i in n:
		print(i, end=' ')
	print()


for i in range(int(input())):
	size = int(input())
	arr = sorted(list(map(int, input().split())))
	for j in range(size - 1):
		if j % 2 != 0:
			temp = arr[j]
			arr[j] = arr[j + 1]
			arr[j + 1] = temp
	string = ' '
	arr1 = list(map(str, arr))
	print(string.join(arr1))


T = int(input())
for t in range(0, T):
	N = int(input())
	A = list(map(int, input().split()))
	lena = len(A)
	temp = sorted(A, reverse=True)
	half2 = temp[:lena // 2]
	half1 = temp[lena // 2:]
	final = []
	for i in range(0, lena // 2):
		final.append(half1[i])
		final.append(half2[i])
	if lena % 2 != 0:
		final.append(half1[-1])
	s = ' '.join([str(elem) for elem in final])
	print(s)


import numpy as np
T = int(input())
for k in range(T):
	N = int(input())
	temp = list(map(int, input().split()))
	A = np.array(temp)
	A = np.sort(A)
	B = np.copy(A)
	for i in range((N - 1) // 2):
		B[2 * i + 1] = A[2 * i + 2]
		B[2 * i + 2] = A[2 * i + 1]
	print(' '.join((str(int(x)) for x in B)))


for i in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	for i in range(n - 1):
		if i % 2 == 0:
			if L[i] > L[i + 1]:
				(L[i], L[i + 1]) = (L[i + 1], L[i])
		elif L[i] < L[i + 1]:
			(L[i], L[i + 1]) = (L[i + 1], L[i])
	print(*L)


import math
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	res = math.ceil(n / 2) - 1
	val = 1
	for j in range(res):
		temp = l[val]
		l[val] = l[val + 1]
		l[val + 1] = temp
		val += 2
	for x in l:
		print(x, end=' ')
	print()


test_cases = int(input())
for _ in range(test_cases):
	size_of_array = int(input())
	input_array = [*map(int, input().split())]
	input_array.sort()
	last_index = 0
	for i in range(0, size_of_array // 2):
		print(input_array[i], end=' ')
		print(input_array[-1 - i], end=' ')
		last_index = i
	if size_of_array % 2 != 0:
		print(input_array[last_index + 1])
	print('\n')


for i in range(int(input())):
	x = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	list2 = []
	v = 0
	b = -1
	count = 0
	for k in range(x):
		if count % 2 == 0:
			list2.append(list1[v])
			v += 1
		else:
			list2.append(list1[b])
			b -= 1
		count += 1
	var = ' '.join(map(str, list2))
	print(var)


n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	xx = sorted(l)
	xxx = sorted(l, reverse=True)
	ll = []
	for i in range(len(l)):
		if len(ll) < len(l):
			ll.append(xx[i])
		if len(ll) < len(l):
			ll.append(xxx[i])
	print(*ll)


import math
t = int(input())
for i in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	lis2 = [0] * n
	lis3 = []
	for j in range(math.ceil(n / 2)):
		lis2[j * 2] = lis[j]
	c = 0
	for j in range(math.ceil(n / 2), n):
		lis2[c * 2 + 1] = lis[j]
		c += 1
	for j in lis2:
		print(j, end=' ')
	print()


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	B = A[:]
	i = 1
	while i <= N - 1:
		if i % 2 != 0 and i + 1 <= N - 1:
			B[i] = A[i + 1]
		elif i % 2 != 0 and i + 1 > N - 1:
			B[i] = A[i]
		else:
			B[i] = A[i - 1]
		i += 1
	arrangedElements = ' '.join(list(map(str, B)))
	print(arrangedElements)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	ans = []
	for i in range(n):
		if i % 2 == 0:
			ans.append(a.pop(0))
		else:
			ans.append(a.pop())
	print(*ans)


def compare(i):
	if i % 2:
		if A[i] < A[i + 1]:
			(A[i], A[i + 1]) = (A[i + 1], A[i])
	elif A[i] > A[i + 1]:
		(A[i], A[i + 1]) = (A[i + 1], A[i])
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	for i in range(n - 1):
		compare(i)
	print(' '.join(map(str, A)))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = 0
	b = len(l) - 1
	while a <= b:
		print(l[a], end=' ')
		if a == b:
			break
		print(l[b], end=' ')
		a += 1
		b -= 1
	print()


import math
n = int(input())
for i in range(n):
	m = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	l2 = [0] * m
	for i in range(math.ceil(m / 2)):
		l2[i * 2] = lis[i]
	c = 0
	for i in range(math.ceil(m / 2), m):
		l2[c * 2 + 1] = lis[i]
		c += 1
	for i in l2:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	for j in range(a - 1):
		if j % 2 == 0 and b[j] > b[j + 1]:
			(b[j], b[j + 1]) = (b[j + 1], b[j])
		elif j % 2 != 0 and b[j] < b[j + 1]:
			(b[j], b[j + 1]) = (b[j + 1], b[j])
	print(' '.join(map(str, b)))


for j in range(int(input())):
	n = int(input())
	lt1 = list(map(int, input().split()))
	lt1.sort()
	lt2 = []
	x = 0
	for i in range(0, n):
		if i % 2 == 0:
			lt2.append(str(lt1[x]))
			x += 1
		else:
			lt2.append(str(lt1[n - x]))
	print(' '.join(lt2))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if n > 2:
		for i in range(1, n - 1, 2):
			(l[i], l[i + 1]) = (l[i + 1], l[i])
	for i in l:
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	l = int(input())
	lis = list(map(int, input().split()))
	ma = []
	mi = []
	op = []
	lis.sort()
	d = l // 2
	if l == 2:
		mi.append(lis[0])
		ma.append(lis[1])
	elif l % 2 == 0:
		mi = lis[0:d]
		ma = lis[d:l]
	else:
		mi = lis[0:d + 1]
		ma = lis[d + 1:l]
	for j in range(min(len(mi), len(ma))):
		op.append(mi[j])
		op.append(ma[j])
	if len(mi) > len(ma):
		op.append(mi[-1])
	print(' '.join((str(x) for x in op)))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	for i in range(1, N, 2):
		if i + 1 < N:
			(A[i], A[i + 1]) = (A[i + 1], A[i])
	print(*A)


import math
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	x = math.ceil(N / 2)
	s = ''
	for (i, j) in zip(A[:x], A[x:]):
		s += str(i) + ' ' + str(j) + ' '
	if N % 2 == 1:
		s += str(A[:x][-1]) + ' '
	print(s[:-1])


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


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	for i in range(1, n - 1, 2):
		(a[i], a[i + 1]) = (a[i + 1], a[i])
	for i in a:
		print(i, end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	kaka = n // 2
	midterm = 0
	for j in range(0, n // 2):
		if j == kaka - 1 and n % 2 == 0:
			print(a[j], end=' ')
			print(a[-j - 1])
		else:
			print(a[j], end=' ')
			print(a[-j - 1], end=' ')
		midterm += 1
	if n % 2 == 1:
		print(a[midterm])


for i in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort()
	for i in range(1, x):
		if i % 2 == 1 and i != x - 1:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
	ans = ''
	for j in l:
		ans = ans + str(j) + ' '
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	j = 0
	a.sort()
	while j < (n + 1) // 2:
		b.append(a[j])
		if j < n - 1 - j:
			b.append(a[n - 1 - j])
		j = j + 1
	print(*b)


t = int(input(''))
for itera in range(t):
	n = int(input(''))
	a = list(map(int, input().split()))
	a.sort()
	ae = a[:(n + 1) // 2]
	ao = a[(n + 1) // 2:]
	ae.sort()
	ao.sort(reverse=True)
	if n == len(a):
		for i in range(n // 2):
			print(ae[i], end=' ')
			print(ao[i], end=' ')
		if n % 2 == 1:
			print(ae[-1], end=' ')
		print()


def rearrange(arr):
	arr.sort()
	for i in range(1, len(arr) - 1, 2):
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return arr
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = rearrange(a)
	for x in ans:
		print(x, end=' ')
	print('')


t = int(input())
for _ in range(t):
	n = int(input())
	integers = list(map(int, input().split()))
	integers.sort()
	for i in range(n):
		if i % 2 == 0 and i != 0:
			temp = integers[i]
			integers[i] = integers[i - 1]
			integers[i - 1] = temp
	print(*integers)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1):
		if i % 2 == 0 and a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
		elif i % 2 != 0 and a[i] < a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	str1 = ' '.join((str(e) for e in a))
	print(str1)


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


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = []
	l.sort()
	k = 0
	for j in range(n):
		if j % 2 == 0:
			r.append(l[k])
		else:
			r.append(l[n - 1 - k])
			k += 1
	print(' '.join(list(map(str, r))))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 1):
		if i % 2 == 0:
			if a[i] >= a[i + 1]:
				temp = a[i + 1]
				a[i + 1] = a[i]
				a[i] = temp
		elif i % 2 != 0:
			if a[i] <= a[i + 1]:
				temp = a[i + 1]
				a[i + 1] = a[i]
				a[i] = temp
	print(*a)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = list()
	a.sort()
	k = 0
	for j in range(n):
		if j % 2 == 0:
			x = a[k]
		else:
			x = a[n - 1 - k]
			k += 1
		r.append(x)
	print(' '.join(list(map(str, r))))


T = int(input())
for z in range(T):
	N = input()
	A = list(map(int, input().split()))
	B = []
	A.sort()
	k = -1
	g = 0
	for i in range(len(A)):
		if i % 2 == 0:
			B.append(A[g])
			g += 1
		elif i % 2 != 0:
			B.append(A[k])
			k -= 1
	for i in range(len(B)):
		print(B[i], end=' ')
	print()


T = int(input())
for i in range(T):
	N = int(input())
	initial = input()
	A = [int(i) for i in initial.split()]
	A.sort()
	for i in range(1, len(A) - 1, 2):
		(A[i], A[i + 1]) = (A[i + 1], A[i])
	print(*A)


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


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	arr.sort()
	i = 1
	while i + 1 < n:
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		i += 2
	print(' '.join((str(x) for x in arr)))


for i in range(int(input())):
	n = int(input())
	a = [int(num) for num in input().split()]
	for j in range(n - 1):
		if j % 2 == 0:
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
		elif a[j] < a[j + 1]:
			(a[j], a[j + 1]) = (a[j + 1], a[j])
	for k in range(n):
		print(a[k], end=' ')
	print(' ', end='\n')


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	for i in range(n - 1):
		if i % 2 == 0:
			if A[i] <= A[i + 1]:
				continue
			else:
				(A[i], A[i + 1]) = (A[i + 1], A[i])
		elif A[i] >= A[i + 1]:
			continue
		else:
			(A[i + 1], A[i]) = (A[i], A[i + 1])
	print(*A)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	for i in range(n):
		if i % 2:
			print(a[n - 1 - i // 2], end=' ')
		else:
			print(a[i // 2], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	array.sort()
	output = ['0'] * n
	mid = (n + 1) // 2
	for i in range(mid):
		output[2 * i] = str(array[i])
	for i in range(n // 2):
		output[2 * i + 1] = str(array[i + mid])
	print(' '.join(output))


for i in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	for i in range(n - 1):
		if i % 2 != 0:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(' '.join(map(str, a)))


t = int(input())
for i in range(t):
	k = int(input())
	a = list(map(int, input().split()))
	for i in range(k - 1):
		if i % 2 == 0:
			if a[i] >= a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		elif a[i] <= a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(*a)


t = int(input())
for i in range(t):
	n = int(input())
	list_a = list(map(int, input().split()))
	list_a.sort()
	new = []
	x = 0
	for j in range(n):
		if j % 2 == 0:
			new.append(list_a[x])
			x += 1
		else:
			new.append(list_a[n - x])
	print(*new)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	for j in range(n - 1):
		if j % 2 == 0 and arr[j] > arr[j + 1]:
			(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		elif j % 2 != 0 and arr[j] < arr[j + 1]:
			(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
	print(' '.join(map(str, arr)))


t = int(input())
for i in range(t):
	n = int(input())
	A = input().split()
	for i in range(n - 1):
		if i % 2 == 0:
			if int(A[i]) >= int(A[i + 1]):
				(A[i], A[i + 1]) = (A[i + 1], A[i])
		elif int(A[i]) <= int(A[i + 1]):
			(A[i], A[i + 1]) = (A[i + 1], A[i])
	print(' '.join(A))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	for j in range(n):
		if j % 2 == 1 and l[j] != l[-1]:
			(l[j], l[j + 1]) = (l[j + 1], l[j])
	for k in l:
		print(k, end=' ')
	print()