JJ loves playing with medians. He has an array A of length N (N is odd). He wants to partition the array A into two non-empty subsets P and Q such that the value of |median(P) - median(Q)| is as small as possible. (Note that each A_{i} must belong to either subset P or subset Q).

Help him find this minimum value of |median(P) - median(Q)|.

As a reminder, the median of a subset X of size N is the element which occupies the \lfloor\frac{N+1}{2}\rfloor^{th} position after we sort the elements in non-decreasing order. For example, median([3, 1, 4]) = 3, median([3, 1, 4, 2]) = 2. (Here \lfloor x \rfloor denotes the largest integer which does not exceed x).

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

- The first line contains T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

Output the minimum value of |median(P) - median(Q)|.

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

$1 ≤ T ≤ 100$
$3 ≤ N ≤ 999$
$1 ≤ A_{i} ≤ 10^{9}$
$N$ is odd.

----- Sample Input 1 ------ 
3
5
2 7 4 8 2
3
1 2 3
5
1 1 1 1 1

----- Sample Output 1 ------ 
2
1
0
----- explanation 1 ------ 
- Test case $1$: We can divide the array into following two subsets: $P = [2, 8], Q = [7, 4, 2]$, which has $|median(P) - median(Q)| = |2 - 4| = 2$. It can be proven that the answer can not be improved further.
- Test case $2$: We can divide the array into following two subsets: $P = [1, 3], Q = [2]$, which has $|median(P) - median(Q)| = |1 - 2| = 1$. It can be proven that the answer can not be improved further.
- Test case $3$: Observe that, for any partition of the array into any two non-empty subsets, the median of both the subsets will be $1$. Therefore the answer is $|1 - 1| = 0$.

Difficulty: MEDIUM
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	print(arr[N // 2] - arr[N // 2 - 1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if n % 2 == 1:
		print(abs(a[(n - 1) // 2] - a[(n - 1) // 2 - 1]))
	elif n % 4 == 0:
		print(abs(a[n // 2 - 1] - a[n // 2 - 2]))
	else:
		print(abs(a[n // 2] - a[n // 2 - 1]))


t = int(input())
for i in range(t):
	n = int(input())
	z = list(map(int, input().split()))
	z = sorted(z)
	ans = 99999999
	print(z[n // 2] - z[n // 2 - 1])


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = (len(a) + 1) // 2
	c = abs(a[b - 1] - a[b - 2])
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = len(a)
	k = b // 2
	j = b // 2 - 1
	print(a[k] - a[j])


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


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	(p, q) = ([], [])
	flag = True
	for i in arr:
		if flag:
			p.append(i)
		else:
			q.append(i)
		flag ^= True
	p1 = len(p)
	q1 = len(q)
	ans = abs(p[(p1 + 1) // 2 - 1] - q[(q1 + 1) // 2 - 1])
	print(ans)


for i in range(int(input())):
	n = int(input())
	nlist = list(map(int, input().split()))
	nlist.sort()
	plist = []
	qlist = []
	check = True
	for j in nlist:
		if check:
			plist.append(j)
		else:
			qlist.append(j)
		check ^= True
	n1 = len(plist)
	n2 = len(qlist)
	print(abs(plist[(n1 + 1) // 2 - 1] - qlist[(n2 + 1) // 2 - 1]))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	f = (n + 1) // 2
	if f % 2 == 0:
		print(abs(arr[f - 1] - arr[f - 2]))
	else:
		print(abs(arr[f - 1] - arr[f - 2]))


import math
alf = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007

def createDic(nums):
	dic = dict()
	for i in nums:
		if not i in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	return dic

def subarray_sum_max(nums):
	array = []
	suma_parcial = 0
	max_sum = 0
	index = 0
	se_refresco = True
	for i in range(len(nums)):
		suma_parcial += nums[i]
		if max_sum < suma_parcial:
			if se_refresco:
				array = []
				se_refresco = False
				index = i
			max_sum = suma_parcial
		if suma_parcial < 0:
			suma_parcial = 0
			se_refresco = True
		elif not se_refresco:
			array.append(nums[i])
	return (array, index, max_sum)

def particiones(nums, index, array):
	if index == len(nums):
		count = 0
	else:
		for i in array:
			i.append(nums[index])
			particiones(nums, index + 1, array)
			i.pop(len(i) - 1)
		array.append([])
		array[len(array) - 1].append(nums[index])
		particiones(nums, index + 1, array)
		array.pop(len(array) - 1)

def busqueda_binaria(nums, x, a_insertar):
	izq = 0
	der = len(nums) - 1
	while izq <= der:
		medio = int((izq + der) / 2)
		if nums[medio] == x:
			return medio
		elif nums[medio] > x:
			der = medio - 1
		else:
			izq = medio + 1
	if a_insertar:
		nums.insert(medio + 1, x)
	return -1

def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	A = []
	B = []
	active = True
	for i in range(n // 2):
		if active:
			A.append(nums[i])
			A.append(nums[n - i - 1])
		else:
			B.append(nums[i])
			B.append(nums[n - i - 1])
		active = not active
	mini1 = 10 ** 9
	mini2 = mini1
	A1 = A.copy()
	A1.append(nums[(n + 1) // 2 - 1])
	A1.sort()
	B.sort()
	if len(B) != 0 and len(A1) != 0:
		mini1 = abs(A1[(len(A1) + 1) // 2 - 1] - B[(len(B) + 1) // 2 - 1])
	B.append(nums[(n + 1) // 2 - 1])
	A.sort()
	B.sort()
	if len(B) != 0 and len(A) != 0:
		mini2 = abs(A[(len(A) + 1) // 2 - 1] - B[(len(B) + 1) // 2 - 1])
	print(min(mini1, mini2))
test = int(input())
while test != 0:
	solve()
	test -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	x = (n + 1) // 2
	if x % 2:
		print(abs(l[x - 1] - l[x - 2]))
	else:
		print(abs(l[x - 2] - l[x - 1]))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	x = (n + 1) // 2
	if x % 2:
		print(abs(l[x - 1] - l[x - 2]))
	else:
		print(abs(l[x - 2] - l[x - 1]))


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


for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	nli.sort()
	x = (n - 1) // 2
	y = (n - 1) // 2 - 1
	mn = abs(nli[x] - nli[y])
	print(mn)


T = int(input())
for i in range(0, T):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	p = n // 2
	print(l[p] - l[p - 1])


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	res = lis[int(n / 2)] - lis[int(n / 2) - 1]
	print(res)


import sys, math, string, random, array
count = 0
max = 0
min = 99

def solve():
	n = int(input())
	x = (n - 1) // 2 - 1
	arr = list(map(int, input().split()))
	arr.sort()
	print(arr[x + 1] - arr[x])
t = int(input())
for i in range(t):
	solve()


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	l.sort()
	print(l[len(l) // 2] - l[len(l) // 2 - 1])


def mgc(arr, n):
	arr.sort()
	return abs(arr[(n - 3) // 2] - arr[(n - 3) // 2 + 1])
	return min(temp[1] - temp[0], temp[2] - temp[1])
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(mgc(arr, n))


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort()
	med = x // 2
	print(l[med] - l[med - 1])


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a1 = [char for char in a[::2]]
	a2 = [cahr for cahr in a[1::2]]
	result = abs(a1[(len(a1) + 1) // 2 - 1] - a2[(len(a2) + 1) // 2 - 1])
	print(result)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	nums.sort()
	diff = nums[int(n / 2)] - nums[int(n / 2) - 1]
	print(diff)


for _ in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	list2 = []
	list3 = []
	for i in range(n):
		if i % 2 == 0:
			list2.append(list1[i])
		else:
			list3.append(list1[i])
	a = len(list2)
	b = len(list3)
	if a % 2 == 0:
		med1 = list2[(a + 1) // 2 - 1]
	else:
		med1 = list2[a // 2]
	if b % 2 == 0:
		med2 = list3[(b + 1) // 2 - 1]
	else:
		med2 = list3[b // 2]
	print(abs(med1 - med2))


for s in [*open(0)][2::2]:
	arr = sorted(map(int, s.split()))
	x = len(arr) // 2
	print(arr[x] - arr[x - 1] if len(arr) % 2 else arr[x + 1] - arr[x])


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


import math

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		A = [int(x) for x in input().split()]
		A.sort()
		l1 = []
		l2 = []
		for i in range(len(A)):
			if i % 2 == 0:
				l1.append(A[i])
			else:
				l2.append(A[i])
		print(abs(l1[(len(l1) + 1) // 2 - 1] - l2[(len(l2) + 1) // 2 - 1]))
		t -= 1
main()


pi = int(input())
while pi != 0:
	n = int(input())
	l = list(input().split())
	for i in range(len(l)):
		l[i] = int(l[i])
	l.sort()
	print(abs(l[len(l) // 2] - l[len(l) // 2 - 1]))
	pi -= 1


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


t = int(input(''))
c = []
for i in range(0, t):
	e = int(input())
	n = list(map(int, input().split(' ')))
	b = sorted(n)
	print(b[e // 2] - b[e // 2 - 1])


t = int(input())
for i in range(t):
	a = int(input())
	l = list(map(int, input().split()))
	new_list = sorted(l)
	middle = a // 2
	middle_left = middle - 1
	ans = new_list[middle] - new_list[middle_left]
	print(ans)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()][:n]
	a.sort()
	print(a[int(n / 2)] - a[int(n / 2 - 1)])


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	print(a[int(n / 2)] - a[int(n / 2) - 1])


from itertools import permutations as per
from math import factorial as fact
from difflib import SequenceMatcher
import bisect

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

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	print(a[n // 2] - a[n // 2 - 1])


for i in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = int(N / 2)
	print(a[c] - a[c - 1])


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))[:n]
	a.sort()
	print(a[n // 2] - a[n // 2 - 1])


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[n // 2] - a[n // 2 - 1])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	a = arr[n // 2]
	b = arr[(n - 2) // 2]
	print(a - b)


try:
	T = int(input())
	for _ in range(T):
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		x = (n - 1) // 2 - 1
		print(a[x + 1] - a[x])
except:
	pass


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	mid = (n - 3) // 2
	print(lst[mid + 1] - lst[mid])


t = int(input())
while t:
	t -= 1
	n = int(input())
	l = [int(x) for x in input().split()]
	l = l[:n]
	l.sort()
	print(abs(l[n // 2] - l[n // 2 - 1]))


t = int(input())
for _ in range(t):
	n = int(input())
	seq = list(map(int, input().split()))
	seq.sort()
	k = n // 2
	print(abs(seq[k - 1] - seq[k]))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	print(a[n // 2] - a[n // 2 - 1])


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


t = int(input())
while t > 0:
	n = int(input())
	li = list(map(int, input().strip().split()))
	li.sort()
	ans = li[n // 2] - li[n // 2 - 1]
	print(ans)
	t -= 1


n = int(input())
while n:
	l = int(input())
	arr1 = [int(l) for l in input().split()]
	arr = sorted(arr1)
	div = (len(arr) + 1) // 2
	mid = div - 1
	ans = abs(arr[mid] - arr[mid - 1])
	print(ans)
	n -= 1


for ih in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans = 10 ** 9 + 7
	mid = l[n // 2]
	for i in range(n // 2):
		ans = min(ans, abs(mid - l[i]))
	print(ans)


try:

	def solve(nums):
		nums.sort()
		return nums[len(nums) // 2] - nums[len(nums) // 2 - 1]
	t = int(input())
	for _ in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		print(solve(l))
except:
	pass


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	mid = n // 2
	print(abs(arr[mid] - arr[mid - 1]))


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s.sort()
	print(s[n // 2] - s[n // 2 - 1])


t = int(input())
for test in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l1 = []
	l2 = []
	c1 = 0
	c2 = 0
	for i in range(n):
		if i % 2 == 0:
			l1.append(l[i])
			c1 += 1
		else:
			l2.append(l[i])
			c2 += 1
	a = (c1 - 1) // 2
	b = (c2 - 1) // 2
	print(abs(l1[a] - l2[b]))