You are given an array with $N$ integers: $A[1], A[2], \ldots, A[N]$ (where $N$ is even). You are allowed to permute the elements however you want. Say, after permuting the elements, you end up with the array $A'[1], A'[2], \ldots, A'[N]$. Your goal is to maximize the following sum:
|A′[1]−A′[2]| + |A′[3]−A′[4]| + ... + |A′[N−1]−A′[N]||A′[1]−A′[2]| + |A′[3]−A′[4]| + ... + |A′[N−1]−A′[N]|
|A'[1] - A'[2]| \ + \ |A'[3] - A'[4]| \ + \ ... \ + \ |A'[N - 1] - A'[N]|

Here, $|x|$ denotes the absolute value of $x$.
You have to print the maximum sum achievable.

-----Input-----
- The first line contains $T$, the number of test cases.
- Each test case starts with an integer $N$ in the first line.
- The second line of each test case contains $N$ space separated integers, denoting the values of array $A$.

-----Output-----
For each test case, output the maximum sum achievable in a new line.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le N \le 10^5$
- $N$ is even
- $|A[i]| \le 10^9$
- Sum of $N$ over all test cases $\le 2 * 10^5$

-----Example Input 1-----
1
4
1 -3 2 -3

-----Example Output 1-----
9

-----Explanation 1-----
The original array is {$1, -3, 2, -3$}. Suppose you permute it and get the array {$2, 1, -3, -3$}. Then the corresponding sum would be $|2 - 1| \ + \ |-3 - (-3)| = 1 + 0 = 1$.
But suppose you permute it differently and get the array {$-3, 2, 1, -3$}. Then the corresponding sum would be $|-3 - 2| \ + \ |1 - (-3)| = 5 + 4 = 9$. You can check that you cannot do any better, and hence the answer is 9.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))[:n]
	m.sort()
	t = 0
	for j in range(n // 2):
		t += abs(m[j] - m[n - j - 1])
	print(t)


T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))[:N]
	L.sort()
	c = 0
	for j in range(N // 2):
		c += abs(L[j] - L[N - j - 1])
	print(c)


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


n = int(input())
l = []
for i in range(0, n):
	a = int(input())
	x = list(map(int, input().split()))
	x.sort()
	total = 0
	b = a // 2
	for j in range(0, b):
		total = total + abs(x[a - j - 1] - x[j])
	l.append(total)
for i in l:
	print(i)


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


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


for t in range(int(input())):
	n = int(input())
	a = sorted([int(i) for i in input().split()])
	s = 0
	if n % 2 == 0:
		i = 0
		j = n - 1
		while i < j:
			s += abs(a[j] - a[i])
			j -= 1
			i += 1
	else:
		s = a[n // 2]
		while i < j:
			s += abs(a[j] - a[i])
			j -= 1
			i += 1
	print(s)


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


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	sum = 0
	for k in range(n // 2):
		sum = sum + abs(arr[n - k - 1] - arr[k])
	print(sum)


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


from fractions import Fraction
for i in range(int(input())):
	N = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	su = 0
	for i in range(N // 2):
		su = su + abs(a[i] - a[N - 1 - i])
	print(su)


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


for _ in range(int(input())):
	n = int(input())
	nums = sorted(list(map(int, input().split())))
	res = sum(nums[n // 2:]) - sum(nums[:n // 2])
	print(res)


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


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


t = int(input())
for i in range(t):
	res = 0
	n = int(input())
	l1 = list(map(int, input().split()))
	l1.sort()
	for i in range(n // 2):
		res = res + abs(l1[i] - l1[n - i - 1])
	print(res)