Read problems statements in Mandarin Chinese and Russian as well. 
Special Sum of 4 numbers (a, b, c, d) is defined as:
|a+b-c-d| + |a+c-b-d| + |a+d-b-c| + |c+d-a-b| + |b+d-a-c| + |b+c-a-d|

where |x| denotes absolute value of x.
Read problems statements in Mandarin Chinese and Russian as well. 
Special Sum of 4 numbers (a, b, c, d) is defined as:
|a+b-c-d| + |a+c-b-d| + |a+d-b-c| + |c+d-a-b| + |b+d-a-c| + |b+c-a-d|

where |x| denotes absolute value of x.
Given an array A of size N, you need to find the sum of Special Sum of numbers taken over all quadruples of different indices of the array. 
 
------ Input ------ 

First line contains T, the number of test cases to follow.
First line of each test case contains the only integer N.
Second line of each test case contains the array as N space separated integers.

------ Output ------ 

For each test case output the sum as explained above.

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

$1 ≤ T ≤ 100$
$4 ≤ N ≤ 1000$
$1 ≤ Elements of the array ≤ 10^{5}$
$1 ≤ Sum of N over all test case ≤ 2000$

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

4

1 2 3 3

5

1 2 3 4 5

6

9 18 28 23 12 9
----- Sample Output 1 ------ 
10

76

1176

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Mathematics


Solutions:
def fun(a, n):
	s = 0
	for i in range(n):
		s += a[i] * (i - (n - i - 1))
	return s * 2
T = int(input())
for i in range(T):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	b = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			b.append(a[i] + a[j])
	b.sort()
	e = fun(b, len(b))
	f = fun(a, n)
	g = e - f * (n - 2)
	print(g)


def fun(a, n, s):
	for i in range(n):
		s += a[i] * (i - (n - i - 1))
	return s * 2
for _ in range(int(input())):
	(n, a, b) = (int(input()), sorted(list(map(int, input().split()))), [])
	for i in range(n - 1):
		for j in range(i + 1, n):
			b.append(a[i] + a[j])
	b.sort()
	print(fun(b, len(b), 0) - fun(a, n, 0) * (n - 2))


def simpleQue(arr):
	(N, ans) = (len(arr), 0)
	arr = sorted(arr)
	for i in range(N):
		ans += (i - (N - i - 1)) * arr[i] * 2
	return ans
for T in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	newArr = []
	for i in range(N):
		for j in range(i + 1, N):
			newArr.append(arr[i] + arr[j])
	print(simpleQue(newArr) - (N - 2) * simpleQue(arr))