There are $n$ bricks numbered from $1$ to $n$. Brick $i$ has a weight of $a_i$.

Pak Chanek has $3$ bags numbered from $1$ to $3$ that are initially empty. For each brick, Pak Chanek must put it into one of the bags. After this, each bag must contain at least one brick.

After Pak Chanek distributes the bricks, Bu Dengklek will take exactly one brick from each bag. Let $w_j$ be the weight of the brick Bu Dengklek takes from bag $j$. The score is calculated as $|w_1 - w_2| + |w_2 - w_3|$, where $|x|$ denotes the absolute value of $x$.

It is known that Bu Dengklek will take the bricks in such a way that minimises the score. What is the maximum possible final score if Pak Chanek distributes the bricks optimally?


-----Input-----

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 2 \cdot 10^4$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the number of bricks.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the weights of the bricks.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a line containing an integer representing the maximum possible final score if Pak Chanek distributes the bricks optimally.


-----Examples-----

Input
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
Output
6
63
0


-----Note-----

In the first test case, one way of achieving a final score of $6$ is to do the following:

Put bricks $1$, $4$, and $5$ into bag $1$.

Put brick $3$ into bag $2$.

Put brick $2$ into bag $3$.

If Pak Chanek distributes the bricks that way, a way Bu Dengklek can take the bricks is:

Take brick $5$ from bag $1$.

Take brick $3$ from bag $2$.

Take brick $2$ from bag $3$.

The score is $|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6$. It can be shown that Bu Dengklek cannot get a smaller score from this distribution.

It can be shown that there is no other distribution that results in a final score bigger than $6$.

Difficulty: MEDIUM
Tags: Greedy algorithms

Sorting

Game theory

Constructive algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
t = int(input())
out = []

def solve(arr):
	arr = sorted(arr)
	max1 = abs(arr[-1] - arr[-2]) + abs(arr[-1] - arr[0])
	for i in range(len(arr) - 2, 1, -1):
		temp = abs(arr[i] - arr[i - 1]) + abs(arr[i] - arr[0])
		if temp > max1:
			max1 = temp
	max2 = abs(arr[-1] - arr[-3]) + abs(arr[-2] - arr[-3])
	for i in range(len(arr) - 3, 0, -1):
		temp = abs(arr[i] - arr[i - 1]) + abs(arr[i - 1] - arr[-1])
		if temp > max2:
			max2 = temp
	return max(max1, max2)
for tc in range(t):
	n = int(input())
	arr = []
	arr = map(int, input().split())
	out.append(solve(arr))
for o in out:
	print(o)


def get_score(one, two, three):
	return abs(one - two) + abs(two - three)

def solution(num_list: list, length: int):
	num_list.sort()
	high = 0
	for i in range(length - 2):
		value = num_list[i + 1] - num_list[i] + num_list[-1] - num_list[i]
		if value > high:
			high = value
	for i in range(1, length - 1):
		value = num_list[i + 1] - num_list[i] + num_list[i + 1] - num_list[0]
		if value > high:
			high = value
	return high
t = int(input())
for _ in range(t):
	n = int(input())
	ln = list(map(int, input().split()))
	print(solution(ln, n))


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return list(map(int, sys.stdin.readline().split()))

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	n = inp()
	l = sorted(values())
	if len(l) == 1:
		print(0)
		return
	if len(l) == 2:
		print(2 * abs(l[0] - l[1]))
		return
	ans = 0
	for i in range(len(l) - 1):
		ans = max(ans, l[-1] - l[i] + l[i + 1] - l[i])
	for i in range(len(l) - 1):
		ans = max(ans, l[i + 1] - l[0] + l[i + 1] - l[i])
	print(ans)
for i in range(inp()):
	solve()


def solve() -> None:
	n = int(input())
	weights = list(map(int, input().split()))
	weights.sort()
	ans = 0
	for i in range(2, n):
		ans = max(ans, weights[i] - weights[i - 1] + weights[i] - weights[0])
	for i in range(1, n - 1):
		ans = max(ans, weights[i] - weights[i - 1] + weights[-1] - weights[i - 1])
	print(ans)
tt = int(input())
for _ in range(tt):
	solve()


def sol(lst):
	res = 0
	lst.sort()
	for i in range(1, n):
		res = max(res, 2 * lst[i] - lst[i - 1] - lst[0])
	for i in reversed(range(len(lst) - 2)):
		res = max(res, lst[n - 1] + lst[i + 1] - 2 * lst[i])
	return res
T = int(input())
for test_case in range(1, T + 1):
	n = int(input())
	lst = list(map(int, input().split()))
	s = sol(lst)
	print(s)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	co = 0
	l = list(set(l))
	l.sort()
	n = len(l)
	if n <= 1:
		co = 0
	elif n == 2:
		co = 2 * (l[1] - l[0])
	else:
		co = l[-1] - l[0] + max(l[-1] - l[-2], l[1] - l[0])
		a = l[-1] - l[1] + l[2] - l[1]
		b = l[-2] - l[0] + l[-2] - l[-3]
		co = max(a, b, co)
		for i in range(2, n - 2):
			c = l[-1] - l[i] + l[i + 1] - l[i]
			e = l[i] - l[0] + l[i] - l[i - 1]
			co = max(co, c, e)
	print(co)


def f(arr):
	s_arr = sorted(arr)
	res = 0
	for i in range(len(arr) - 2):
		res = max([res, s_arr[i + 1] - s_arr[i] + s_arr[-1] - s_arr[i]])
	for i in range(len(arr) - 1, 1, -1):
		res = max([res, s_arr[i] - s_arr[i - 1] + s_arr[i] - s_arr[0]])
	return res
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	print(f(arr))


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


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		m_a = min(a)
		M_a = max(a)
		init_val = max(M_a - m_a + a[1] - m_a, M_a - m_a + M_a - a[-2])
		for i in range(1, n - 1):
			val1 = M_a - a[i] + a[i + 1] - a[i]
			j = n - i - 1
			val2 = a[j] - m_a + a[j] - a[j - 1]
			val = max(val1, val2)
			if val > init_val:
				init_val = val
		print(init_val)
main()


for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	ans = arr[-1] - arr[0]
	for i in range(n - 1):
		b1 = arr[i + 1]
		b2 = arr[-1]
		b3 = arr[0]
		ans = max(ans, b1 + b2 - 2 * arr[i], 2 * b1 - arr[i] - b3)
	print(ans)


def bar(A):
	res = 0
	for i in range(1, len(A) - 1):
		ma = A[i - 1]
		res = max(res, A[i] - ma + A[-1] - ma)
	return res

def foo():
	N = int(input())
	A = sorted(list(map(int, input().strip().split())))
	B = [-x for x in A][::-1]
	return max(bar(A), bar(B))
T = int(input())
for _ in range(T):
	print(foo())


def min_score(bricks):
	bricks_n = sorted(bricks)
	bricks.sort(reverse=True)
	score = 0
	for k in range(len(bricks) - 2):
		score = max(score, bricks_n[k + 1] - 2 * bricks_n[k] + bricks_n[-1])
	for k in range(len(bricks_n) - 2):
		score = max(score, 2 * bricks[k] - bricks[k + 1] - bricks[-1])
	return score
a = int(input())
for i in range(a):
	f = int(input())
	bricks = list(map(int, input().split()))
	print(min_score(bricks))


t = int(input())
for t1 in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	ans = 0
	for i in range(n - 1):
		mx = a[i + 1] - a[i] + max(a[i + 1] - a[0], a[-1] - a[i])
		if mx > ans:
			ans = mx
	print(ans)


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


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	v1 = 0
	v2 = 0
	for i in range(n - 1, 1, -1):
		v1 = max(2 * a[i] - a[i - 1] - a[0], v1)
	for i in range(0, n - 2):
		v2 = max(a[i + 1] + a[-1] - 2 * a[i], v2)
	return max(v1, v2)
for t in range(0, int(input())):
	print(solve())


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(key=lambda x: -x)
	answer = 0
	for i in range(n - 2):
		v = 2 * a[i] - a[i + 1] - a[n - 1]
		if v > answer:
			answer = v
	for j in range(2, n):
		v = a[0] + a[j - 1] - 2 * a[j]
		if v > answer:
			answer = v
	print(answer)


import math
t = int(input())

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


t = int(input())
for _ in range(t):
	input()
	temp = input().split()
	l = [int(v) for v in temp]
	l.sort()
	largest = 0
	for b in range(0, len(l) - 2):
		m = abs(l[b] - l[b + 1]) + abs(l[b] - l[-1])
		if m > largest:
			largest = m
	l.reverse()
	for b in range(0, len(l) - 2):
		m = abs(l[b] - l[b + 1]) + abs(l[b] - l[-1])
		if m > largest:
			largest = m
	print(largest)


def brick():
	t = int(input())
	for i in range(t):
		n = int(input())
		para = input().split(' ')
		bri = [int(x) for x in para]
		bri.sort()
		(s, l) = (bri[0], bri[-1])
		e1 = l - s + max(min(bri[1:-1]) - s, l - max(bri[1:-1]))
		for i in range(1, len(bri) - 1):
			e2 = l - bri[i - 1] + bri[i] - bri[i - 1]
			e3 = bri[i + 1] - bri[i] + bri[i + 1] - s
			e1 = max(e1, e2, e3)
		print(e1)
brick()


import sys, os
if os.path.exists('a.txt'):
	sys.stdin = open('a.txt', 'r')
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for i in range(n - 1):
		ans = max(ans, a[i + 1] - a[i] + a[n - 1] - a[i])
		ans = max(ans, a[i + 1] - a[i] + a[i + 1] - a[0])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mx = 0
	w = sorted(a)
	for i in range(n - 1):
		mx = max(mx, w[-1] - w[i] + w[i + 1] - w[i], w[i + 1] - w[i] + w[i + 1] - w[0])
	print(mx)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	a.sort()
	v1 = max((2 * a[i] - a[i - 1] - a[0] for i in range(n - 1, 1, -1)))
	v2 = max((a[i + 1] + a[-1] - 2 * a[i] for i in range(n - 2)))
	return max(v1, v2)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = solve(a, n)
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	lis = [int(i) for i in input().split()]
	lis.sort()
	max = 0
	for i in range(2, n):
		if max < 2 * lis[i] - lis[i - 1] - lis[0]:
			max = 2 * lis[i] - lis[i - 1] - lis[0]
	for i in range(n - 1):
		if max < lis[i + 1] + lis[n - 1] - 2 * lis[i]:
			max = lis[i + 1] + lis[n - 1] - 2 * lis[i]
	print(max)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(j) for j in input().split()]
	a.sort()
	result = 0
	for i in range(1, n - 1):
		result = max(result, 2 * a[i + 1] - a[0] - a[i])
		result = max(result, a[n - 1] + a[i] - 2 * a[i - 1])
	print(result)


def solve(arr, n):
	arr.sort()
	maxx = 0
	for i in range(1, n - 1):
		maxx = max(maxx, abs(arr[i + 1] - arr[0]) + abs(arr[i + 1] - arr[i]))
	for i in range(0, n - 2):
		maxx = max(maxx, abs(arr[n - 1] - arr[i]) + abs(arr[i + 1] - arr[i]))
	print(maxx)
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	solve(arr, n)


t = int(input())
while t > 0:
	n = int(input())
	b = list(map(int, input().split()))
	b.sort()
	ans = 0
	first = b[0]
	last = b[-1]
	for bri in range(2, n):
		br = b[bri]
		ans1 = br - first + br - b[bri - 1]
		if ans1 > ans:
			ans = ans1
	for bri in range(0, n - 2):
		br = b[bri]
		ans1 = last - br + b[bri + 1] - br
		if ans1 > ans:
			ans = ans1
	print(ans)
	t -= 1


t = int(input())
for j in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	max = a[n - 1] - a[0]
	for i in range(0, len(a) - 1):
		if max < a[n - 1] - a[i] + a[i + 1] - a[i]:
			max = a[n - 1] - a[i] + a[i + 1] - a[i]
	for i in range(len(a) - 1, 0, -1):
		if max < a[i] - a[0] + a[i] - a[i - 1]:
			max = a[i] - a[0] + a[i] - a[i - 1]
	print(max)


import sys

def read():
	return [int(x) for x in sys.stdin.readline().split(' ')]
[t] = read()
for _ in range(t):
	[n] = read()
	A = read()
	A.sort()
	res = A[n - 1] - A[0]
	for i in range(1, n - 1):
		res = max(res, 2 * A[i + 1] - A[i] - A[0])
	for i in range(0, n - 2):
		res = max(res, A[n - 1] + A[i + 1] - 2 * A[i])
	print(res)


t = int(input(''))
for j in range(t):
	n = int(input(''))
	l = list(map(int, input('').split()))
	l.sort()
	m = 0
	for i in range(-1, -len(l) + 1, -1):
		a = l[i] + l[i] - l[i - 1] - l[0]
		if m < a:
			m = a
	for i in range(0, n - 2):
		a = l[-1] + l[i + 1] - l[i] - l[i]
		if m < a:
			m = a
	print(m)


casecnt = int(input())
for case in range(casecnt):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	bestscore = 0
	for i in range(1, n):
		g = a[i] - a[i - 1]
		score = g
		score += max(a[i] - a[0], a[n - 1] - a[i - 1])
		bestscore = max(score, bestscore)
	print(bestscore)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	ans = arr[n - 1] - arr[0]
	for i in range(n - 1):
		ans = max(ans, arr[n - 1] + arr[i + 1] - 2 * arr[i], 2 * arr[i + 1] - arr[i] - arr[0])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	lst_a = sorted(map(int, input().split()))
	mx = 0
	for j in range(n):
		mx = max(mx, 2 * lst_a[j] - lst_a[0] - lst_a[j - 1])
	for j in range(n - 1):
		mx = max(mx, lst_a[-1] + lst_a[j + 1] - 2 * lst_a[j])
	print(mx)


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


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	ans = 0
	for i in range(1, n - 1):
		ans = max(ans, a[i] - a[i - 1] + a[-1] - a[i - 1])
	for i in range(1, n - 1):
		ans = max(ans, a[-i] - a[-1 - i] + a[-i] - a[0])
	print(ans)
	t -= 1


def sol(lst):
	lst.sort()
	maxi = 0
	for i in range(2, len(lst)):
		maxi = max(maxi, abs(lst[i] - lst[i - 1]) + abs(lst[i] - lst[0]))
	for i in reversed(range(len(lst) - 2)):
		maxi = max(maxi, abs(lst[i] - lst[i + 1]) + abs(lst[i] - lst[-1]))
	return maxi
T = int(input())
for test_case in range(1, T + 1):
	n = int(input())
	lst = [int(s) for s in input().split(' ')]
	s = sol(lst)
	print(s)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	b = [2 * a[-1] - a[0] - a[-2], a[-1] + a[1] - 2 * a[0]]
	for i in range(1, n - 1):
		b.append(max(a[i] - a[0] + a[i] - a[i - 1], a[-1] - a[i] + a[i + 1] - a[i]))
	print(max(b))


test_case_count = int(input())
for _ in range(test_case_count):
	brick_no = int(input())
	brick_weights = list(map(int, input().split()))
	brick_weights = sorted(brick_weights)
	ans = 0
	for i in range(1, brick_no):
		ans = max(ans, brick_weights[i] - brick_weights[i - 1] + brick_weights[i] - brick_weights[0])
	for i in range(brick_no - 1):
		ans = max(ans, brick_weights[i + 1] - brick_weights[i] + brick_weights[brick_no - 1] - brick_weights[i])
	print(ans)


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


T = int(input())
for kse in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for i in range(n - 1):
		ans = max(ans, max(a[i + 1] - a[0] + a[i + 1] - a[i], a[n - 1] - a[i] + a[i + 1] - a[i]))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	ans = 0
	for i in range(n):
		if i < n - 2:
			res = A[i + 1] - A[i] + A[n - 1] - A[i]
			ans = max(ans, res)
		if i >= 2:
			res = A[i] - A[i - 1] + A[i] - A[0]
			ans = max(ans, res)
	print(ans)


from collections import deque
import sys

def solve_problem():
	t = int(sys.stdin.readline())
	for _ in range(t):
		n = int(sys.stdin.readline())
		arr = list(map(int, sys.stdin.readline().split()))
		arr.sort()
		res = 0
		for i in range(1, n):
			res = max(res, abs(arr[i] - arr[i - 1]) + arr[i] - arr[0])
		for i in range(n - 1):
			res = max(res, abs(arr[i + 1] - arr[i]) + abs(arr[i] - arr[n - 1]))
		print(res)
solve_problem()


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


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	a.sort()
	ans = 0
	for i in range(n):
		if i == 0:
			ans = max(ans, a[1] + a[n - 1] - 2 * a[0])
		elif i == n - 1:
			ans = max(ans, -a[0] - a[n - 2] + 2 * a[n - 1])
		else:
			ans = max(ans, a[i + 1] + a[n - 1] - 2 * a[i])
	for i in range(n):
		if i == 0:
			ans = max(ans, a[1] + a[n - 1] - 2 * a[0])
		elif i == n - 1:
			ans = max(ans, -a[0] - a[n - 2] + 2 * a[n - 1])
		else:
			ans = max(ans, -a[i - 1] - a[0] + 2 * a[i])
	print(ans)
(tt,) = inp_arr()
for t in range(tt):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = sorted(a)
	mx = a[-1]
	mn = a[0]
	a1 = a[0]
	an_1 = a[-1]
	for e in a:
		if e != mn:
			a1 = e
			break
	for i in range(n - 1, -1, -1):
		if a[i] != mx:
			an_1 = a[i]
			break
	ans = max(2 * a[-1] - a[0] - an_1, a[-1] - a[0] + a1 - a[0])
	pre = a1
	for i in range(2, n):
		if a[i] != pre:
			ans = max(ans, 2 * a[i] - a[0] - pre)
			pre = a[i]
	pre = an_1
	for i in range(n - 2, -1, -1):
		if a[i] != pre:
			ans = max(ans, mx - a[i] + pre - a[i])
			pre = a[i]
	print(ans)


import sys
import math
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	ans = 0
	for i in range(1, n):
		ans = max(ans, abs(l[i] - l[i - 1]) + l[i] - l[0])
	for i in range(n - 1):
		ans = max(ans, abs(l[-1] - l[i]) + abs(l[i + 1] - l[i]))
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = abs(a[0] - a[n - 1]) + abs(a[n - 1] - a[n - 2])
	ans = max(ans, abs(a[n - 1] - a[0]) + abs(a[0] - a[1]))
	for i in range(2, n):
		ans = max(ans, abs(a[0] - a[i]) + abs(a[i] - a[i - 1]))
	for i in range(0, n - 2):
		ans = max(ans, abs(a[n - 1] - a[i]) + abs(a[i] - a[i + 1]))
	print(ans)
	t -= 1


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


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	mnToMx = 0
	for i in range(n - 2):
		mnToMx = max(mnToMx, abs(a[i] - a[i + 1]) + abs(a[i] - a[n - 1]))
	mxToMn = 0
	i = n - 1
	while i >= 2:
		mxToMn = max(mxToMn, abs(a[i] - a[i - 1]) + abs(a[i] - a[0]))
		i -= 1
	print(max(mxToMn, mnToMx))


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


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	maxx = 0
	for j in range(2, n):
		maxx = max(maxx, abs(a[0] - a[j]) + abs(a[j] - a[j - 1]))
	for k in range(n - 2):
		maxx = max(maxx, abs(a[n - 1] - a[k]) + abs(a[k] - a[k + 1]))
	print(maxx)


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


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


import sys
import math
from bisect import bisect_right as br
import threading

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	arr.sort()
	ans = 0
	for i in range(2, n):
		ans = max(ans, abs(arr[i] - arr[0]) + abs(arr[i] - arr[i - 1]))
	for i in range(n - 2):
		ans = max(ans, abs(arr[i] - arr[n - 1]) + abs(arr[i] - arr[i + 1]))
	print(ans)


case = int(input())
for i in range(case):
	n = int(input())
	mas = list(map(int, input().split()))
	mas.sort()
	cur_max = 0
	for j in range(1, len(mas) - 1):
		cur_min = mas[j - 1]
		cur_max = max(cur_max, mas[-1] - 2 * cur_min + mas[j])
		cur_min = mas[len(mas) - j]
		cur_max = max(cur_max, 2 * cur_min - mas[0] - mas[len(mas) - j - 1])
	print(cur_max)


t = int(input())
for _ in range(t):
	n = int(input())
	w = list(map(int, input().split(' ')))
	w1 = sorted(w)
	w2 = sorted(w, reverse=True)
	answer = 0
	for i in range(n - 2):
		answer = max(answer, abs(w1[i] - w1[i + 1]) + abs(w1[i] - w1[n - 1]), abs(w2[i] - w2[i + 1]) + abs(w2[i] - w2[n - 1]))
	print(answer)


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


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	a.sort()
	ans = 0
	for i in range(n - 1):
		ans = max(ans, abs(a[i + 1] - a[i]) + abs(a[i] - a[n - 1]))
	for i in range(1, n):
		ans = max(ans, abs(a[i] - a[i - 1]) + a[i] - a[0])
	print(ans)


T = int(input())
for tt in range(T):
	n = int(input())
	data = list(map(int, input().split()))
	data = sorted(data)
	subtract = []
	for i in range(1, n):
		subtract.append(data[i] - data[i - 1])
	ans = 0
	the_sum = sum(subtract)
	for i in range(len(subtract) - 1):
		ans = max(ans, the_sum + max(subtract[i], subtract[-1]))
		the_sum -= subtract[i]
	the_sum = sum(subtract)
	for i in range(len(subtract) - 1, 0, -1):
		ans = max(ans, the_sum + max(subtract[i], subtract[0]))
		the_sum -= subtract[i]
	print(ans)


from typing import List

def test_case():
	n = int(input())
	nums: List[int]
	nums = sorted([int(item) for item in input().split()])
	max_f = max(nums[n - 1] - nums[0] + nums[n - 1] - nums[n - 2], nums[1] - nums[0] + nums[n - 1] - nums[0])
	for i in reversed(range(1, n - 1)):
		max_f = max(max_f, nums[i] - nums[i - 1] + nums[i] - nums[0])
	for i in range(0, n - 2):
		max_f = max(max_f, nums[n - 1] - nums[i] + nums[i + 1] - nums[i])
	return max_f
t = int(input())
while t > 0:
	t -= 1
	print(test_case())


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	maxi = 0
	for i in range(0, len(l) - 2):
		ans1 = abs(l[i] - l[-1]) + abs(l[-1] - l[-2])
		ans2 = abs(l[-1] - l[i]) + abs(l[i] - l[i + 1])
		maxi = max(maxi, ans1, ans2)
	l.sort(reverse=True)
	maxim = 0
	for j in range(0, len(l) - 2):
		ans1 = abs(l[j] - l[-1]) + abs(l[-1] - l[-2])
		ans2 = abs(l[-1] - l[j]) + abs(l[j] - l[j + 1])
		maxim = max(maxim, ans1, ans2)
	ans = max(maxi, maxim)
	print(ans)


import sys
input = sys.stdin.readline
from random import randint
RANDOM = randint(1, 10 ** 9)

class hf(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(hf, self).__hash__() ^ RANDOM

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	cnt = {}
	for i in range(n):
		hv = hf(arr[i])
		if hv not in cnt:
			cnt[hv] = 0
		cnt[hv] += 1
	m = len(cnt)
	if m == 1:
		return 0
	elif m == 2:
		return 2 * (max(arr) - min(arr))
	else:
		arr = sorted(list(set(arr)))
		(d1, d2) = (arr[1] - arr[0], arr[-1] - arr[-2])
		ans = arr[-1] - arr[0] + max(d1, d2)
		m = len(arr)
		for i in range(2, m):
			ans = max(arr[i] - arr[i - 1] + arr[i] - arr[0], ans)
		for i in range(m - 3, -1, -1):
			ans = max(arr[i + 1] - arr[i] + arr[-1] - arr[i], ans)
		return ans
for _ in range(int(input())):
	print(solve())


t = int(input())
for j in range(0, t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	for k in range(0, n):
		if k == 0:
			s = max(s, abs(l[k] - l[n - 1]) + abs(l[k] - l[1]))
		elif k == n - 1:
			s = max(s, abs(l[k] - l[0]) + abs(l[n - 2] - l[k]))
		else:
			f = max(abs(l[k] - l[0]) + abs(l[k] - l[k - 1]), abs(l[k] - l[0]) + abs(l[k] - l[k + 1]))
			f1 = max(abs(l[k] - l[n - 1]) + abs(l[k] - l[k - 1]), abs(l[k] - l[n - 1]) + abs(l[k] - l[k + 1]))
			f = max(f, f1)
			s = max(s, f)
	print(s)


import heapq
t = int(input())
for i in range(t):
	n = int(input())
	w = [int(k) for k in input().split()]
	w.sort()
	eta = []
	for j in range(2, n):
		eta.append(-(2 * w[j] - w[j - 1]))
	heapq.heapify(eta)
	mx = 0
	check = set()
	for j in range(n - 2):
		mx = max(-eta[0] - w[j], mx)
		check.add(-(2 * w[j + 2] - w[j + 1]))
		while eta and eta[0] in check:
			check.remove(heapq.heappop(eta))
	w = w[::-1]
	eta = []
	for j in range(2, n):
		eta.append(-(w[j - 1] - 2 * w[j]))
	heapq.heapify(eta)
	res = 0
	check = set()
	for j in range(n - 2):
		res = max(w[j] - eta[0], res)
		check.add(-(w[j + 1] - 2 * w[j + 2]))
		while eta and eta[0] in check:
			check.remove(heapq.heappop(eta))
	res = max(mx, res)
	print(res)