Chefina has an array A consisting of N non-negative integers.

The *beauty* of a subsequence S is defined as 3 \cdot 
\texttt{abs(means(S) - median(S))},  
where \texttt{mean(S)} denotes the [mean] of subsequence S and \texttt{median(S)} denotes the [median] of subsequence S.

Now, Chefina asks Chef to choose a subsequence S of size 3 from array A such that the *beauty* of S is minimised. Your task is to find the minimum *beauty* possible.

As a reminder, a subsequence of an array is obtained by deleting some elements from the array without changing the order of the remaining elements.

Note: It can be proven that the answer is always an integer.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of elements in the array.
- The second line contains N space-separated integers, the elements of the array A.

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

For each test case, output on a new line, the minimum *beauty* possible of any subsequence of array A, having length 3.

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

$1 ≤ T ≤ 500$
$3 ≤ N ≤ 5\cdot 10^{3}$
$0  ≤ A_{i} ≤ 10^{9} $
- Sum of $N$ over all test cases does not exceed $5\cdot 10^{3}$. 

------ subtasks ------ 

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
2
4
1 6 8 0
10
5 5 7 0 1 0 4 7 9 4
----- Sample Output 1 ------ 
3
0
----- explanation 1 ------ 
Test case $1$: For the given array $[1, 6, 8, 0]$, Chef will choose the subsequence $[1, 6, 8]$ for minimum beauty.
- The mean of subsequence will be $\frac{(1 + 6 + 8)}{3} = 5$
- The median of subsequence will be $6$ (as it is the middle element after sorting the subsequence). 
- The beauty of the subsequence is $3\cdot$ $\texttt{abs(5-6)}$ $= 3$.

It can be shown that this is the minimum beauty that can be obtained using any subsequence of size $3$.

Test case $2$: For the given array $[5, 5, 7, 0, 1, 0, 4, 7, 9, 4]$, Chef will choose subsequence $[1, 4, 7]$ for minimum beauty.
- The mean of subsequence will be $\frac{(1 + 4 + 7)}{3} = 4$
- The median of subsequence will be $4$ (as it is the middle element after sorting the subsequence). 
- The beauty of the subsequence is $3\cdot$ $\texttt{abs(4-4)}$ $= 0$.

It can be shown that this is the minimum beauty that can be obtained using any subsequence of size $3$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Amortized analysis

Complete search


Solutions:
import math
for _ in range(int(input())):
	n = int(input())
	aa = [int(x) for x in input().split()]
	assert len(aa) == n
	aa.sort()
	mn = math.inf
	for i in range(1, n - 1):
		b = aa[i]
		j = i + 1
		k = i - 1
		dcb = aa[j] - b
		dba = b - aa[k]
		while True:
			vl = abs(dcb - dba)
			if vl < mn:
				mn = vl
			if dcb == dba:
				break
			elif dcb < dba:
				j += 1
				if j >= n:
					break
				dcb = aa[j] - b
			else:
				k -= 1
				if k < 0:
					break
				dba = b - aa[k]
		if mn == 0:
			break
	print(mn)


def T(A, N, k):
	i = 0
	j = N - 1
	min1 = abs(A[i] + A[j] - 2 * A[k])
	while i < k and k < j:
		if A[i] + A[j] - 2 * A[k] == 0:
			return 0
		elif A[i] + A[j] > 2 * A[k]:
			min1 = min(min1, A[i] + A[j] - 2 * A[k])
			j -= 1
		else:
			min1 = min(min1, 2 * A[k] - A[i] - A[j])
			i += 1
	return min1
a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	ans1 = A[2] - A[0]
	ans2 = A[-1] - A[-3]
	ans = T(A, N, 1)
	if ans == 0:
		print(ans)
	else:
		for k in range(1, N - 1):
			ans = min(ans, T(A, N, k))
			if ans == 0:
				break
		if A[0] == A[1]:
			for k in range(2, N):
				ans1 = min(ans1, A[k] - A[0])
			ans = min(ans, ans1)
		if A[-1] == A[-2]:
			for k in range(0, N - 2):
				ans2 = min(ans2, A[-1] - A[k])
			ans = min(ans, ans2)
		print(ans)


n = int(input())
while n:
	x = int(input())
	lis = list(map(int, input().split()))
	lis.sort()
	ans = 10000000000.0
	for b in range(1, x - 1):
		a = b - 1
		c = b + 1
		while a >= 0 and c <= x - 1:
			ans = min(ans, abs(lis[a] + lis[c] - 2 * lis[b]))
			if lis[c] - lis[b] > lis[b] - lis[a]:
				a -= 1
			else:
				c += 1
		if ans == 0:
			break
	print(ans)
	n -= 1


import math

def bvalue(arr, i, k, j):
	return abs(arr[i] + arr[j] - 2 * arr[k])
case = int(input())
for _ in range(case):
	n = int(input())
	arr = sorted(list(map(int, input().split(' '))))
	res = math.inf
	for i in range(n):
		k = i + 1
		for j in range(i + 2, n):
			while k + 1 < j:
				if bvalue(arr, i, k, j) > bvalue(arr, i, k + 1, j):
					k += 1
					continue
				break
			res = min(res, bvalue(arr, i, k, j))
			if res == 0:
				break
	print(res)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	m = math.inf
	for i in range(1, n - 1):
		x = ar[i]
		j = i + 1
		k = i - 1
		c = ar[j] - x
		d = x - ar[k]
		while True:
			val = abs(c - d)
			if val < m:
				m = val
			if c == d:
				break
			elif c < d:
				j += 1
				if j >= n:
					break
				c = ar[j] - x
			else:
				k -= 1
				if k < 0:
					break
				d = x - ar[k]
		if m == 0:
			break
	print(m)


import math
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = math.inf
	for j in range(1, n - 1):
		b = l[j]
		k = j + 1
		i = j - 1
		while True:
			a = l[i]
			c = l[k]
			val = abs(a + c - 2 * b)
			m = min(m, val)
			if c - b == b - a:
				break
			elif c - b > b - a:
				i -= 1
				if i < 0:
					break
			else:
				k += 1
				if k >= n:
					break
		if m == 0:
			break
	print(m)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = math.inf
	for j in range(1, n - 1):
		b = a[j]
		k = j + 1
		m = j - 1
		dcb = a[k] - b
		dba = b - a[m]
		while True:
			vl = abs(dcb - dba)
			if vl < l:
				l = vl
			if dcb == dba:
				break
			elif dcb < dba:
				k += 1
				if k >= n:
					break
				dcb = a[k] - b
			else:
				m -= 1
				if m < 0:
					break
				dba = b - a[m]
		if l == 0:
			break
	print(l)


t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	res = float('inf')
	for i in range(1, n - 1):
		x = A[i]
		L = []
		for j in range(i - 1, -1, -1):
			L.append(x - A[j])
		k = 0
		for j in range(i + 1, n):
			v = A[j] - x
			while k < len(L) and v >= L[k]:
				k += 1
			if k < len(L):
				res = min(res, abs(v - L[k]))
			if k > 0:
				res = min(res, abs(v - L[k - 1]))
			if res == 0:
				break
		if res == 0:
			break
	print(res)


import math
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = math.inf
	l.sort()
	for i in range(1, n - 1):
		v = l[i]
		j = i + 1
		k = i - 1
		cb = l[j] - v
		ab = v - l[k]
		while True:
			if abs(cb - ab) < m:
				m = abs(cb - ab)
			if cb == ab:
				break
			elif cb < ab:
				j += 1
				if j >= n:
					break
				cb = l[j] - v
			else:
				k -= 1
				if k < 0:
					break
				ab = v - l[k]
		if m == 0:
			break
	print(m)


import bisect, math

def solve(n, arr):
	mini = 10 ** 9
	for i in range(n):
		for j in range(i + 2, n):
			if arr[i] == arr[j] or mini == 0:
				return 0
			avg = math.ceil((arr[i] + arr[j]) / 2)
			pos = bisect.bisect_left(arr, avg, i, j)
			mini = min(mini, abs(arr[i] + arr[j] - 2 * arr[pos]), abs(arr[i] + arr[j] - 2 * arr[pos - 1]))
	return mini
for _ in range(int(input())):
	print(solve(int(input()), sorted(list(map(int, input().split())))))


import sys, math, cmath, time
from bisect import bisect_left
start_time = time.time()

def solve():
	n = inp()
	a = [int(k) for k in inps()]
	a.sort()
	ans = 1000000000000.0
	for i in range(1, n - 1):
		k = a[i]
		l = i - 1
		r = i + 1
		while l < i and l >= 0 and (r > i) and (r < n):
			avg = a[l] + a[i] + a[r]
			ans = min(ans, abs(avg - 3 * k))
			if avg == k:
				ans = 0
				break
			if avg < 3 * k:
				r += 1
			else:
				l -= 1
	print(int(ans))

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		solve()

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


from bisect import bisect_left
import math
for tt in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = float('inf')
	arr.sort()
	chk = False
	for i in range(n):
		for j in range(i + 2, n):
			if arr[i] == arr[j] or ans == 0:
				ans = 0
				chk = True
				break
			pos = bisect_left(arr, math.ceil((arr[i] + arr[j]) / 2), i + 1, j - 1)
			ans = min(ans, abs(arr[i] + arr[j] - 2 * arr[pos]), abs(arr[i] + arr[j] - 2 * arr[pos - 1]))
		if chk:
			break
	print(ans)


def beauty(l1, l2, a):
	l1.sort(reverse=True)
	l2.sort()
	i = 0
	j = 0
	ans = 10000000000000
	while i < len(l1) and j < len(l2):
		ans = min(ans, abs(a - l1[i] - l2[j]))
		if l1[i] + l2[j] > a:
			i += 1
		else:
			j += 1
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = 10000000001
	for i in range(1, n - 1):
		if beauty(a[:i], a[i + 1:], a[i] * 2) < b:
			b = beauty(a[:i], a[i + 1:], a[i] * 2)
	print(b)


from sys import stdin

def solve():
	n = int(stdin.readline())
	arr = sorted(map(int, stdin.readline().split()))
	best = 10 ** 10
	for left in range(n):
		i = left + 1
		for right in range(left + 2, n):
			s = arr[left] + arr[right]
			x = arr[i]
			while 2 * x < s:
				i += 1
				x = arr[i]
			if i == left + 1:
				score = abs(s - 2 * x)
			elif i == right:
				score = abs(s - 2 * arr[i - 1])
			else:
				s1 = abs(s - 2 * x)
				s2 = abs(s - 2 * arr[i - 1])
				if s1 < s2:
					score = s1
				else:
					score = s2
			if score < best:
				best = score
	print(best)

def main():
	for _ in range(int(stdin.readline())):
		solve()
main()


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = []
	mi = []
	for k in range(1, n - 1):
		i = k - 1
		j = k + 1
		x = l[i] - l[k]
		y = l[j] - l[k]
		s = x + y
		m.append(abs(s))
		while i > 0 or j < n - 1:
			if s > 0 and i > 0:
				i = i - 1
				s = s + l[i] - l[i + 1]
				m.append(abs(s))
			elif s < 0 and j < n - 1:
				j = j + 1
				s = s + l[j] - l[j - 1]
				m.append(abs(s))
			else:
				break
		mi.append(min(m))
		m = []
	print(min(mi))


import math
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	ans = math.inf
	for mid in range(1, len(arr) - 1):
		left = mid - 1
		right = mid + 1
		while True:
			left_difference = arr[mid] - arr[left]
			right_difference = arr[right] - arr[mid]
			difference = abs(left_difference - right_difference)
			if difference < ans:
				ans = difference
			if left_difference == right_difference:
				ans = 0
				break
			elif left_difference > right_difference:
				right += 1
				if right == len(arr):
					break
			else:
				left -= 1
				if left == -1:
					break
		if ans == 0:
			break
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	aa = [int(x) for x in input().split()]
	assert len(aa) == n
	aa.sort()
	mn = math.inf
	for i in range(1, n - 1):
		b = aa[i]
		j = i + 1
		k = i - 1
		c = aa[j]
		a = aa[k]
		while True:
			v1 = c - b
			v2 = b - a
			vl = abs(v1 - v2)
			if vl < mn:
				mn = vl
			if v1 == v2:
				break
			elif v1 < v2:
				j += 1
				if j >= n:
					break
				c = aa[j]
			else:
				k -= 1
				if k < 0:
					break
				a = aa[k]
	print(mn)


def min_beauty(a):
	min_mean = float('inf')
	a.sort()
	n = len(a)
	res = float('inf')
	for i in range(1, n - 1):
		(l, r) = (0, n - 1)
		while l < i and i < r:
			sum = a[l] + a[r]
			if sum == 2 * a[i]:
				return 0
			if sum > 2 * a[i]:
				r -= 1
			else:
				l += 1
			min_mean = min(min_mean, abs(sum - 2 * a[i]))
		res = min(res, min_mean)
	return res
for z in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(min_beauty(l))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	mini = 10000000000.0
	for i in range(1, n - 1):
		a = 0
		b = 2 * arr[i]
		c = n - 1
		while a < i and c > i:
			new = arr[a] + arr[c] - b
			if new < 0:
				a += 1
			else:
				c -= 1
			mini = min(mini, abs(new))
			if mini == 0:
				break
		else:
			continue
		break
	print(mini)


t = int(input())
for i in range(t):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	i = 1
	main = 10000000000
	while i < n - 1:
		j = i - 1
		k = i + 1
		while j >= 0 and k < n:
			if main > abs(A[j] + A[k] - 2 * A[i]):
				main = abs(A[j] + A[k] - 2 * A[i])
			if A[j] + A[k] >= 2 * A[i]:
				j = j - 1
			else:
				k = k + 1
		if main == 0:
			break
		i = i + 1
	print(main)