Read problems statements in mandarin chinese, russian and vietnamese as well. 

You are given an array A of size 2 * N consisting of positive integers, where N is an odd number. You can construct an array B from A as follows, B[i] = max(A[2 * i - 1], A[2 * i]), i.e. B array contains the maximum of adjacent pairs of array A. Assume that we use 1-based indexing throughout the problem.

You want to maximize the median of the array B. For achieving that, you are allowed to permute the entries of A. Find out the maximum median of corresponding B array that you can get. Also, find out any permutation for which this maximum is achieved.

------ Note ------ 

Median of an array of size n, where n is odd, is the middle element of the array when it is sorted in non-decreasing order. Note that n being odd, the middle element will be unique, i.e. at index (n+1) / 2.

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

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N.
The second line of each test case contains 2 * N space separated integers denoting array A.

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

For each test case, output two lines.
The first of which should contain an integer corresponding to maximum value of the median of array B that you can get.
In the second line, print 2 * N integers in a single line denoting any permutation of A for which the maximum value of median of array B is achieved.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 50000$
$1 ≤ A_{i} ≤ 2 * N$

------ Subtasks ------ 

$Subtask #1 (25 points) : 1 ≤ N ≤ 3$
$Subtask #2 (75 points) : original constraints$

----- Sample Input 1 ------ 
3
1
1 2
3
1 2 3 4 5 6
3
1 3 3 3 2 2
----- Sample Output 1 ------ 
2
1 2
5
1 3 2 5 4 6
3
1 3 3 3 2 2
----- explanation 1 ------ 
Example case 1. There are only two possible permutations of A, for both of those B will be 2. The median of B is 2.

Example case 2. For following permutation of A: 1 3 2 5 4 6, the corresponding B will be: 3 5 6, whose median is 5, which is the maximum that you can achieve.

Example case 3. For A: 1 3 3 3 2 2, the corresponding B will be: 3, 3, 2. Its 
median is 3, which is maximum that you can achieve.

Source: codechef | Difficulty: MEDIUM
Tags: Sorting

Greedy algorithms


Solutions:
n = int(input())
while n:
	n -= 1
	N = int(input())
	l = [int(x) for x in input().split()]
	b = []
	l.sort()
	for i in range(N):
		b.append(l[i])
		b.append(l[N + i])
	print(b[N])
	print(*b)


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


for T in range(int(input())):
	N = int(input())
	nums = sorted(list(map(int, input().split())))
	result = [0] * (2 * N)
	list_pointer = 2 * N - 1
	for index in range(list_pointer, -1, -2):
		result[index] = nums[list_pointer]
		list_pointer -= 1
	store_pointer = 0
	for index in range(list_pointer + 1):
		result[store_pointer] = nums[index]
		store_pointer += 2
	print(max(result[N], result[N - 1]))
	print(*result)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	brr = []
	for i in range(n):
		brr.append(arr[i])
		brr.append(arr[n + i])
	print(brr[n])
	print(*brr)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	a = arr[n:2 * n]
	print(a[n // 2])
	for i in range(n):
		print(arr[i], arr[n + i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	Arr = sorted(list(map(int, input().split())))
	b_Arr = Arr[n:2 * n]
	print(b_Arr[n // 2])
	for i in range(n):
		print(Arr[i], Arr[n + i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(a, b) = (a[:n // 2 * 2], a[n // 2 * 2:])
	c = []
	for i in range(len(b) // 2):
		c.append(b[i])
		c.append(b[i + n // 2 + 1])
	print(c[1])
	print(' '.join((str(x) for x in a + c)))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	a1 = arr[:n]
	a2 = arr[n:]
	print(arr[n + n // 2])
	for i in range(n):
		print(a1[i], a2[i], end=' ')
	print()


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = []
	for j in range(length):
		ans.append(arr[j])
		ans.append(arr[-j - 1])
	median_pos = length + length // 2
	print(arr[median_pos])
	print(*ans)


for _ in range(int(input())):
	N = int(input())
	arr = sorted(list(map(int, input().split())))
	B_arr = arr[N:2 * N]
	print(B_arr[N // 2])
	for i in range(N):
		print(arr[i], arr[N + i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()[:2 * n]))
	lst.sort()
	l1 = lst[n:2 * n]
	print(l1[n // 2])
	for i in range(n):
		print(lst[i], lst[n + i], end=' ')
	print()


def CreateDic(nums):
	dic = dict()
	for i in nums:
		if not i in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	return dic
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	numsA = []
	for i in range(1, n + 1):
		numsA.append(nums[i - 1])
		numsA.append(nums[i - 1 + n])
	numsB = []
	for i in range(n, 2 * n):
		numsB.append(nums[i])
	print(numsB[int(len(numsB) / 2)])
	for i in numsA:
		print(i, end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	res = arr[n:2 * n]
	print(res[n // 2])
	for i in range(n):
		print(arr[i], arr[n + i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	Ai = list(map(int, input().split()))
	Ai.sort()
	Aip = []
	for i in range(n):
		Aip.extend([Ai[i], Ai[n + i]])
	print(Aip[n])
	print(*Aip)


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = l[:n]
	b = l[n:2 * n]
	m = []
	for i in range(n):
		m.append(a[i])
		m.append(b[n - 1 - i])
	print(l[3 * n // 2])
	for i in m:
		print(i, end=' ')
	print('\n')


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(a[2 * n - 1 - (n - 1) // 2])
	B = []
	for i in range(n):
		B.append(str(a[i]))
		B.append(str(a[i + n]))
	print(' '.join(B))


t = int(input())
for i in range(t):
	n = int(input())
	s = input().split()
	l = []
	for j in s:
		l.append(int(j))
	l.sort()
	p = n + n // 2
	m = l[p]
	s1 = ''
	for k in range(n):
		s1 += str(l[k]) + ' ' + str(l[k + n]) + ' '
	print(m)
	print(s1)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	val = l[n:]
	print(val[len(val) // 2])
	for i in range(n):
		print(l[i], l[n + i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	mdn = a[n + n // 2]
	b = []
	for i in range(n):
		b.append(a[i])
		b.append(a[n + i])
	print(mdn)
	print(*b)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	print(arr[(3 * n - 1) // 2])
	for i in range(n):
		print(arr[i], arr[n + i], end=' ')
	print()


for _ in range(int(input())):
	N = int(input())
	st = input().split()
	A = []
	for x in st:
		A.append(int(x))
	A.sort()
	p = N + N // 2
	M = A[p]
	st = ''
	for k in range(N):
		st += str(A[k]) + ' ' + str(A[k + N]) + ' '
	print(M)
	print(st)


import math
from math import log2, sqrt
import sys
sys.setrecursionlimit(pow(10, 6))
import collections
from collections import defaultdict
from statistics import median
inf = float('inf')
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	it1 = 0
	it2 = 2 * n - 1
	m = []
	while it1 < it2:
		m.append(l[it1])
		it1 += 1
		m.append(l[it2])
		it2 -= 1
	b = [0 for i in range(n)]
	for i in range(n):
		b[i] = max(m[2 * i], m[2 * i + 1])
	print(median(b))
	print(*m)


from statistics import median
for _ in range(int(input())):
	N = int(input())
	A = [int(a) for a in input().split()]
	A.sort(reverse=True)
	B = A[:N]
	print(median(B))
	C = []
	for i in range(N):
		C.append(B[i])
		C.append(A[N + i])
	print(' '.join(list(map(str, C))))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	b = a[n:]
	a = a[:n]
	print(b[int(n / 2)])
	for i in range(n):
		print(a[i], b[i], end=' ')
	print('')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	x = [0] * (2 * n)
	c = 0
	for j in range(2 * n - 1, -1, -2):
		x[j] = l[c]
		c += 1
	for j in range(2 * n - 2, -1, -2):
		x[j] = l[c]
		c += 1
	c = n // 2
	ans = max(x[2 * c], x[2 * c + 1])
	print(ans)
	print(*x)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	B = A[N:]
	C = A[:N]
	X = []
	p = B[N // 2]
	print(p)
	for (i, j) in zip(B, C):
		X.append(i)
		X.append(j)
	print(*X)


t = int(input())
for i in range(t):
	s = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	hold = int(s / 2)
	print(arr[2 * s - 1 - hold])
	for j in range(s):
		print(arr[j], arr[2 * s - 1 - j], end=' ', sep=' ')
	print()


import numpy as np
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	m = N * 3 // 2
	x = np.partition(A, m)[m]
	H = [i for i in range(0, 2 * N, 2) if A[i] >= x and A[i + 1] >= x]
	L = [i for i in range(0, 2 * N, 2) if A[i] < x and A[i + 1] < x]
	for (h, l) in zip(H, L[:len(H)]):
		(A[h], A[l]) = (A[l], A[h])
	print(x)
	print(*A)


for _ in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	A.sort()
	z = A[n:]
	print(z[len(z) // 2])
	for i in range(n):
		print(A[i], A[n + i], end=' ')
	print()


def solve(arr):
	lst = sorted(arr)
	n = len(arr) // 2
	b = []
	final = []
	for i in range(n):
		b.append(max(lst[i], lst[i + n]))
		final.append(lst[i])
		final.append(lst[i + n])
	print(b[len(b) // 2])
	print(' '.join(map(str, final)))
t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	solve(arr)
	t -= 1


import sys
for i in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	a.sort()
	sys.stdout.write(str(a[n:][int((n - 1) / 2)]) + '\n')
	for j in range(n):
		sys.stdout.write(str(a[j]) + ' ' + str(a[n + j]) + ' ')
	sys.stdout.write('\n')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = l[n:]
	m = m[n // 2]
	print(m)
	l2 = []
	for i in range(n):
		l2.append(l[i])
		l2.append(l[2 * n - i - 1])
	print(*l2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = arr[n + n // 2]
	print(ans)
	b = []
	for i in range(n):
		b.append(arr[i])
		b.append(arr[i + n])
	print(*b)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	output = []
	a = l[:n]
	b = l[n:]
	list((output.extend(i) for i in zip(a, b)))
	alpha = int((n - 1) / 2)
	print(b[alpha])
	output = ' '.join(map(str, output))
	print(output)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = l[:n]
	l = l[n:]
	print(l[n // 2])
	for i in range(n):
		print(m[i], l[i], end=' ')
	print()


def cal():
	T = int(input())
	for _ in range(T):
		n = int(input())
		A1 = list(map(int, input().split()))
		A = sorted(A1)
		if n % 2 == 1:
			print(A[n + int(n / 2)])
		else:
			print(max(A[n + int(n / 2)], A[n + int(n / 2) - 1]))
		for i in range(n):
			print(A[i], A[n + i], end=' ')
		print()
cal()


for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().strip().split()))
	arr.sort()
	s1 = str(arr[0])
	print(arr[N // 2 + N])
	for i in range(N):
		print(arr[i], arr[N + i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	list1 = [int(i) for i in input().split()]
	list1.sort()
	number = list1[n:]
	print(number[len(number) // 2])
	for i in range(n):
		print(list1[i], list1[n + i], end=' ')
	print()


def partition(arr, low, high):
	i = low - 1
	pivot = arr[high]
	for j in range(low, high):
		if arr[j] <= pivot:
			i = i + 1
			(arr[i], arr[j]) = (arr[j], arr[i])
	(arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
	return i + 1

def quickSort(arr, low, high):
	if low < high:
		pi = partition(arr, low, high)
		quickSort(arr, low, pi - 1)
		quickSort(arr, pi + 1, high)
for _ in range(int(input())):
	N = int(input())
	arr = list(map(int, input().strip().split()))
	quickSort(arr, 0, len(arr) - 1)
	s1 = str(arr[0])
	print(arr[N // 2 + N])
	for i in range(N):
		print(arr[i], arr[N + i], end=' ')
	print()


n = int(input())
for _ in range(n):
	p = int(input())
	t = [int(j) for j in input().split()]
	t.sort()
	ls = t[p:2 * p]
	d = int((p - 1) / 2)
	print(ls[d])
	q = list()
	for i in range(p):
		q.append(t[i])
		q.append(ls[i])
	print(*q)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = a[:len(a) // 2]
	c = a[len(a) // 2:]
	p = [0] * len(a)
	j = 0
	k = 0
	for i in range(len(p)):
		if i % 2 == 0:
			p[i] = b[j]
			j += 1
		else:
			p[i] = c[k]
			k += 1
	med = p[len(p) // 2]
	print(med)
	for x in p:
		print(x, end=' ')
	print()
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	(b, c) = (l[0:len(l) // 2], l[len(l) // 2:])
	d = []
	for i in range(len(b)):
		d.append(b[i])
		d.append(c[i])
	print(b[len(b) // 2])
	for i in range(len(d)):
		print(d[i], end=' ')
	print('')
	t -= 1


for t in range(int(input())):
	n = 2 * int(input())
	A = list(map(int, input().split()))
	A = list(sorted(A))
	Alow = A[:n // 2]
	Ahigh = A[n // 2:]
	median = Ahigh[n // 4]
	B = []
	for i in range(n // 2):
		B.append(Alow[i])
		B.append(Ahigh[i])
	print(median)
	print(*B)


t = int(input())
while t:
	n = int(input())
	x = n
	y = n + int(n / 2)
	l = list(map(int, input().split()))
	p = []
	q = []
	l.sort()
	z = l[y]
	for i in range(x, 2 * n):
		p.append(l[i])
	for i in range(0, x):
		q.append(l[i])
		q.append(p[i])
	print(z)
	for i in q:
		print(i, end=' ')
	print()
	t -= 1


def permute_max_median(A):
	A.sort()
	median = A[len(A) // 2 + len(A) // 4]
	for i in range(len(A) // 2):
		(A[i * 2 + 1], A[len(A) // 2 + i]) = (A[len(A) // 2 + i], A[i * 2 + 1])
	return median

def main():
	from sys import stdin
	T = int(stdin.readline())
	for t in range(T):
		N = int(stdin.readline())
		A = list((int(a) for a in stdin.readline().split()))
		assert len(A) == N * 2
		print(permute_max_median(A))
		print(*A)
main()


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l, reverse=True)
	e = l[(n - 1) // 2]
	print(e)
	for j in range(n):
		print(l[j], l[n + j], end=' ')
	print('')


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


for t in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	sa = sorted(a)
	b = []
	c = []
	for i in range(n, 2 * n):
		b.append(sa[i])
	for i in range(0, n):
		c.append(sa[i])
	print(b[n // 2])
	for i in range(0, n):
		print(c[i], b[i], end=' ')
	print()


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	l2 = l[:len(l) // 2]
	l1 = l[len(l) // 2:]
	print(l1[len(l1) // 2])
	for i in range(n):
		print(l2[i], l1[i], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	lesser = l[:n]
	greater = l[n:]
	print(greater[n // 2])
	for i in range(n):
		print(lesser[i], greater[i], end=' ')
	print()


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l2 = l[n:2 * n]
	mid = n // 2
	print(l2[mid])
	for i in range(0, n):
		print(l[i], end=' ')
		print(l2[i], end=' ')
	print('\n', end='')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	b = []
	for i in range(n):
		b.append(max(a[i], a[len(a) - 1 - i]))
	if n % 2 == 1:
		print(b[(n - 1) // 2])
	else:
		print(max(b[len(b) // 2 - 1], b[len(b) // 2]))
	for i in range(n):
		print(str(a[i]) + ' ' + str(b[i]), end=' ')
	print('')


for i in range(int(input())):
	n = int(input())
	x = input()
	x = list(map(int, x.split()))
	x.sort()
	y = x[n:]
	print(y[n // 2])
	i = 0
	while i < n:
		print(x[i], x[n + i], end=' ')
		i += 1
	print()


tc = int(input())
for i in range(tc):
	b = []
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	k = 2 * n
	if n == 1:
		print(a[1])
		print(' '.join(map(str, a)))
	else:
		x = 1
		y = n
		while x < y:
			tmp = a[x]
			a[x] = a[y]
			a[y] = tmp
			x += 2
			y += 1
		for j in range(0, k, 2):
			b.append(a[j + 1])
		print(b[n // 2])
		print(' '.join(map(str, a)))


n = int(input())
while n > 0:
	c = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	lb = len(b)
	mid = int(c)
	median = int(2 * c - (c + 1) / 2)
	print(b[median])
	(b[mid], b[median]) = (b[median], b[mid])
	for i in range(c - 1):
		if i % 2 != 0:
			(b[i - 1], b[lb - i - 1]) = (b[lb - i - 1], b[i - 1])
	for r in b:
		print(r, end=' ')
	print()
	n -= 1


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	print(A[-((N + 1) // 2)])
	B = []
	N *= 2
	for i in range(N // 2):
		B.extend([str(A[i]), str(A[i + N // 2])])
	print(' '.join(B))


def quicksort(myList, start, end):
	if start < end:
		pivot = partition(myList, start, end)
		quicksort(myList, start, pivot - 1)
		quicksort(myList, pivot + 1, end)
	return myList

def partition(myList, start, end):
	pivot = myList[start]
	left = start + 1
	right = end
	done = False
	while not done:
		while left <= right and myList[left] <= pivot:
			left = left + 1
		while myList[right] >= pivot and right >= left:
			right = right - 1
		if right < left:
			done = True
		else:
			temp = myList[left]
			myList[left] = myList[right]
			myList[right] = temp
	temp = myList[start]
	myList[start] = myList[right]
	myList[right] = temp
	return right
T = int(input())
for j in range(T):
	n = int(input())
	A = [int(n) for n in input().split()]
	C = quicksort(A, 0, len(A) - 1)
	median = C[2 * n - (n + 1) // 2]
	for i in range((n - 1) // 2):
		d = C[2 * i + 1]
		C[2 * i + 1] = C[2 * n - 2 * i - 1]
		C[2 * n - 2 * i - 1] = d
	print(median)
	print(*C)


T = int(input())
for _ in range(0, T):
	N = int(input())
	a = list(map(int, input().split(' ')))
	a = sorted(a)
	print(a[(3 * N + 1) // 2 - 1])
	print(*[y for x in zip(a[0:N], a[N:2 * N]) for y in x if y is not None])


for _ in range(int(input())):
	(n, a) = (int(input()), sorted([int(x) for x in input().split()]))
	c = []
	for i in range(n):
		c.append(a[i])
		c.append(a[n + i])
	print(c[2 * (n // 2) + 1])
	print(*c)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	up = A[N:]
	down = A[:N]
	print(up[N >> 1])
	A = []
	for (x, y) in zip(down, up):
		A.append(x)
		A.append(y)
	print(' '.join(map(str, A)))


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


t = int(input())
for k in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	if n == 1:
		print(max(a[0], a[1]))
		for i in range(len(a)):
			print(a[i], end=' ')
		print()
	else:
		a.sort()
		b = []
		j = 0
		for i in range(n):
			b.append(a[i])
			b.append(a[2 * n - i - 1])
		print(max(b[n], b[n + 1]))
		for i in range(len(a)):
			print(b[i], end=' ')
		print()
	t = t - 1


cases = int(input())
j = 0
while j < cases:
	j += 1
	n = int(input())
	mid = int((n - 1) / 2)
	a_raw = input().split()
	a = [int(x) for x in a_raw]
	a.sort()
	b = a[1::2]
	for i in range(mid):
		(a[2 * i], a[2 * (n - i - 1)]) = (a[2 * (n - i - 1)], a[2 * i])
		b[i] = max(a[2 * i], b[i])
	b.sort()
	median = b[mid]
	a_raw = [str(x) for x in a]
	print(median)
	print(' '.join(a_raw))


test = input()
test = int(test)
for j in range(0, test):
	n = input()
	n = int(n)
	list2 = []
	list3 = []
	list4 = []
	list2 = list(map(int, input().strip().split(' ')))
	list2.sort()
	print(list2[len(list2) - n // 2 - 1])
	j = len(list2) - 1
	for i in range(0, n, 2):
		(list2[i], list2[j]) = (list2[j], list2[i])
		j -= 1
	for i in range(0, len(list2) - 1):
		print(list2[i], end=' ')
	print(list2[i + 1])


def compose_list(l_idx, sub_len, r_idx, t_list):
	new_list = []
	for iterv in range(sub_len):
		new_list.append(t_list[l_idx])
		l_idx += 1
		new_list.append(t_list[r_idx])
		r_idx += 1
	return new_list
t_num = int(input())
for t_iter in range(t_num):
	t_len = int(input())
	twice_idx = 2 * t_len
	a_list = [-1]
	a_list = a_list + [int(xvar) for xvar in input().split(' ')]
	a_list.sort()
	a_list = [-1] + compose_list(1, t_len, t_len + 1, a_list)
	print(a_list[t_len + 1])
	print(*a_list[1:], sep=' ')


x = int(input())
for i in range(0, x):
	y = int(input())
	q = list(map(int, input().strip().split(' ')))
	q.sort()
	m = q[y:2 * y]
	ans = m[y // 2]
	print(ans)
	for i in range(0, y, 2):
		t = q[i]
		q[i] = q[y]
		q[y] = t
		y = y + 2
	for u in range(0, len(q) - 1):
		print(q[u], end=' ')
	print(q[u + 1])


t = int(input())
while t:
	t = t - 1
	n = int(input())
	b = []
	a = list(map(int, input().split()))
	a.sort()
	a1 = [-1] * (2 * n)
	k1 = 2 * n - 1
	k2 = 0
	for i in range(0, len(a)):
		if i % 2 == 0:
			a1[i] = a[k1]
			k1 -= 1
		else:
			a1[i] = a[k2]
			k2 += 1
	for i in range(0, len(a), 2):
		b.append(a1[i])
	print(b[len(b) // 2])
	for i in range(len(a)):
		print(a1[i], sep=' ', end=' ')
	print()