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: interview

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)

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)

# cook your dish here
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)

# cook your dish here
for _ 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)

# cook your dish here
t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split()))
 a.sort()
 s=0
 for i in range(n//2):
  s+=abs(a[n-i-1]-a[i])
 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)

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_)


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


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

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


# cook your dish here
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) 

# cook your dish here
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)

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())
 a = list(map(int, input().split()))
 a.sort()
 sum = 0
 for i in range(n//2) :
  sum += (a[n-i-1] - a[i])
 print(sum)

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)

# cook your dish here
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)
 


# cook your dish here
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)