Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a sequence $A_{1}, A_{2}, \ldots, A_{N}$. Find the maximum value of the expression $|A_{x}-A_{y}| + |A_{y}-A_{z}| + |A_{z}-A_{x}|$ over all triples of pairwise distinct valid indices $(x, y, z)$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum value of $|A_{x}-A_{y}| + |A_{y}-A_{z}| + |A_{z}-A_{x}|$.

------  Constraints ------
$1 ≤ T ≤ 5$
$3 ≤ N ≤ 10^{5}$
$|A_{i}| ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points): $N ≤ 500$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
3

3

2 7 5

3

3 3 3

5

2 2 2 2 5
----- Sample Output 1 ------ 
10

0

6
----- explanation 1 ------ 
Example case 1: The value of the expression is always $10$. For example, let $x = 1$, $y = 2$ and $z = 3$, then it is $|2 - 7| + |7 - 5| + |5 - 2| = 5 + 2 + 3 = 10$.

Example case 2: Since all values in the sequence are the same, the value of the expression is always $0$.

Example case 3: One optimal solution is $x = 1$, $y=2$ and $z = 5$, which gives $|2 - 2| + |2 - 5| + |5 - 2| = 0 + 3 + 3 = 6$.

Difficulty: EASY
Tags: Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(2 * abs(a[n - 1] - a[0]))


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


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))[:N]
	m = min(A)
	M = max(A)
	print(2 * (M - m))


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	b = lst[n - 1] - lst[0]
	c = lst[n - 1] - lst[1]
	d = lst[1] - lst[0]
	print(b + c + d)


n = int(input())
for i in range(n):
	num = int(input())
	t = input()
	list1 = t.split()
	list2 = []
	for i in list1:
		list2.append(int(i))
	list2.sort()
	a = list2[len(list2) - 1]
	b = list2[(len(list2) - 1) // 2]
	c = list2[0]
	sum = a - c + (b - c) + (a - b)
	print(sum)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(2 * (max(a) - min(a)))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lmax = max(l)
	lmin = min(l)
	p = 0
	l.remove(lmax)
	l.remove(lmin)
	for i in l:
		x = abs(lmax - lmin) + abs(lmax - i) + abs(lmin - i)
		if x > p:
			p = x
	print(p)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	mx = max(a)
	mn = min(a)
	a.remove(mx)
	a.remove(mn)
	p = 0
	for i in a:
		x = abs(i - mn) + abs(mn - mx) + abs(mx - i)
		if x > p:
			p = x
	print(p)


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	print(2 * (max(x) - min(x)))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = min(l)
	b = max(l)
	c = l[-2]
	print(abs(a - b) + abs(b - c) + abs(c - a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ma = max(a)
	mi = min(a)
	b = []
	for i in a:
		b.append(i)
	b.remove(ma)
	b.remove(mi)
	s = abs(mi - b[0]) + abs(b[0] - ma) + abs(ma - mi)
	print(s)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	a = max(l) - min(l)
	print(2 * a)


for i in range(int(input())):
	n = int(input())
	a = [int(num) for num in input().split()]
	a.sort()
	x = a[0]
	y = a[-1]
	z = a[(n - 1) // 2]
	s = abs(x - y) + abs(y - z) + abs(z - x)
	print(s)


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = abs(l[x - 1] - l[1]) + abs(l[x - 1] - l[0]) + abs(l[0] - l[1])
	print(a)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = list(set(a))
	x = min(a)
	z = max(a)
	l = []
	for i in a:
		l.append(abs(x - i) + abs(i - z) + abs(z - x))
	print(max(l))


t = int(input())
for _ in range(t):
	n = int(input())
	xr = sorted(list(map(int, input().split())))
	x = xr[0]
	y = xr[-1]
	z = xr[-2]
	val = abs(x - y) + abs(y - z) + abs(z - x)
	print(val)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(2 * (max(A) - min(A)))


for _ in range(int(input())):
	p = int(input())
	arr = list(map(int, input().split()))
	print(2 * (max(arr) - min(arr)))


def eq(a, b, c):
	return abs(a - b) + abs(b - c) + abs(c - a)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	a = arr[0]
	c = arr[-1]
	m = 0
	for i in arr[1:-1]:
		m = max(m, eq(a, i, c))
	print(m)


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort()
	x.reverse()
	print(2 * x[0] - 2 * x[-1])


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	a = max(lst)
	c = min(lst)
	print(2 * a - 2 * c)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	x = b[0]
	z = b[-1]
	if abs(b[1] - b[0]) <= abs(b[-1] - b[-2]):
		y = b[1]
	else:
		y = b[-2]
	print(abs(x - y) + abs(y - z) + abs(z - x))


def cal(x, y, z):
	print(abs(x - y) + abs(y - z) + abs(x - z))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if len(a) == 3:
		cal(a[0], a[1], a[2])
	else:
		a.sort()
		cal(a[-1], a[0], a[1])


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	l = []
	l.append(max(A))
	A.pop(A.index(max(A)))
	l.append(min(A))
	A.pop(A.index(min(A)))
	s = list(set(A))
	l.append(s[0])
	print(abs(l[0] - l[1]) + abs(l[1] - l[2]) + abs(l[2] - l[0]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	(x, y, z) = (-1, 0, len(l) // 2)
	print(abs(l[x] - l[y]) + abs(l[x] - l[z]) + abs(l[y] - l[z]))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	for j in range(1, n):
		s += l[j] - l[j - 1]
	for j in range(1, n):
		q = l[n - 1] - l[0]
	print(s + q)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	sum = 0
	for j in range(n - 1):
		sum = sum + abs(a[j] - a[j + 1])
	sum = sum + abs(a[-1] - a[0])
	print(sum)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	print(abs(a[0] - a[n - 1]) + abs(a[1] - a[n - 1]) + abs(a[1] - a[0]))


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	b.sort()
	m = abs(b[0] - b[-1])
	n = abs(b[0] - b[-2])
	p = abs(b[-2] - b[-1])
	print(m + n + p)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	l1.sort()
	ans = abs(l1[0] - l1[len(l1) - 1]) + abs(l1[0] - l1[len(l1) - 2]) + abs(l1[len(l1) - 2] - l1[len(l1) - 1])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(2 * (max(a) - min(a)))


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(n) for n in input().split()]
	m = max(a)
	n = min(a)
	print(2 * (m - n))


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


tst = int(input())
for i in range(tst):
	num = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	n = len(arr)
	a1 = arr[n - 1]
	a2 = arr[0]
	a3 = arr[1]
	ans = abs(a1 - a2) + abs(a2 - a3) + abs(a3 - a1)
	print(ans)


t = int(input())
while t:
	n = int(input())
	l = sorted(list(map(int, input().split())))
	a = l[0]
	b = l[1]
	c = l[n - 1]
	print(abs(a - b) + abs(a - c) + abs(b - c))
	t -= 1


for _ in range(int(input())):
	N = int(input())
	S = set(map(int, input().split()))
	if len(S) == 1:
		print(0)
	else:
		print(2 * (max(S) - min(S)))


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = [int(x) for x in input('').split()]
	k = list(t)
	k.sort()
	e = abs(k[0] - k[-1]) + abs(k[-1] - k[x // 2]) + abs(k[0] - k[x // 2])
	print(e)


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


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	print(2 * (max(b) - min(b)))


for _ in range(int(input())):
	i = int(input())
	j = list(map(int, input().split()))
	print((max(j) - min(j)) * 2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	x = [l[0], l[-1], l[-2]]
	res = abs(x[0] - x[1]) + abs(x[1] - x[2]) + abs(x[2] - x[0])
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	maxi = max(ar)
	mini = min(ar)
	print(abs(maxi - mini) * 2)


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	a = max(array)
	b = min(array)
	m = abs(a - b) * 2
	print(m)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = max(l)
	b = min(l)
	print((a - b) * 2)


t = int(input())
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	x = arr[0]
	z = arr[-1]
	if arr[-1] - arr[-2] >= arr[1] - arr[0]:
		y = arr[-2]
	else:
		y = arr[1]
	sum1 = abs(x - y) + abs(y - z) + abs(z - x)
	print(sum1)


def func(num1: int, num2: int, num3: int) -> int:
	return abs(num1 - num2) + abs(num2 - num3) + abs(num3 - num1)
t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	nums.sort()
	min_num = nums[0]
	max_num = nums[-1]
	mid_num = nums[len(nums) // 2]
	max_value_func = func(min_num, mid_num, max_num)
	print(max_value_func)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	f = l[0]
	m = l[1]
	ll = l[-1]
	d = abs(f - m) + abs(m - ll) + abs(ll - f)
	print(d)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	if len(l) >= 3:
		mi = l[0]
		ma = l[-1]
		v = l[1]
		x = abs(mi - v) + abs(v - ma) + abs(ma - mi)
		print(x)


for x in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = set(A)
	C = list(B)
	C.sort()
	if len(C) == 1:
		print('0')
	elif len(C) == 3:
		total = abs(C[0] - C[1]) + abs(C[1] - C[2]) + abs(C[2] - C[0])
		print(total)
	elif len(C) == 2:
		total = abs(C[0] - C[0]) + abs(C[0] - C[1]) + abs(C[1] - C[0])
		print(total)
	elif len(C) > 3:
		total = abs(C[0] - C[1]) + abs(C[1] - C[-1]) + abs(C[-1] - C[0])
		print(total)


vish = int(input())
for vojj in range(vish):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = arr[0]
	mn = mx
	for i in range(n):
		if arr[i] > mx:
			mx = arr[i]
			continue
		if arr[i] < mn:
			mn = arr[i]
	mx = mx - mn
	print(2 * mx)


vish = int(input())
for vojj in range(vish):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = max(arr)
	mn = min(arr)
	mx = mx - mn
	print(2 * mx)


vish = int(input())
for vojj in range(vish):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	print(2 * (arr[-1] - arr[0]))


for test in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())), reverse=True)
	temp_res = abs(a[0] - a[-1])
	res = float('-inf')
	for y in a[1:n - 1]:
		temp = abs(a[0] - y) + abs(y - a[-1]) + temp_res
		res = max(res, temp)
	print(temp)


t = int(input())
for i in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	print(2 * (max(m) - min(m)))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	sum1 = 0
	if n == 3:
		sum1 = abs(arr[-1] - arr[-2]) + abs(arr[-1] - arr[-3]) + abs(arr[-3] - arr[-2])
	elif n > 3:
		sum1 = abs(arr[0] - arr[1]) + abs(arr[0] - arr[-1]) + abs(arr[-1] - arr[1])
	print(sum1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	l.sort()
	for i in range(n):
		a = l[n - 1]
		b = l[0]
		c = l[1]
	print(abs(a - b) + abs(b - c) + abs(c - a))