### PROBLEM LINK:

**Author:** Devendra Agarwal

**Tester:** Surya Kiran

**Editorialist:** Amit Pandey

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

None

### PROBLEM:

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|

You have to find \sum_{i=1}^{N} \sum_{j=i+1}^{N} \sum_{k=j+1}^{N} \sum_{l=k+1}^{N} Special Sum(A[i], A[j], A[k], A[l])

### Solution:

Before solving this problem we will be solving a different version of this problem.

### Problem Version 1:

Given an array A, find the sum of all |a-b| where a and b are from different indices of A.

### Solution for Version 1:

Sort the array A in increasing order.

Now let us find the answer when A_i is used.

A_i is greater than i-1 elements and Less than N-i elements.

Hence the value contributed by A_i will be 2*( (i-1)*A_i - (N-i)*A_i )

Now we can sum this up to find our solution.

Let us call this problem version as Function1(Array A) which will give us the solution of this version.

### Main Problem:

SpecialSum(a,b,c,d) = (|(a+b)-(c+d)| + |(c+d)-(a+b)|) + (|(a+c)-(b+d)| + |(b+d)-(a+c)|) + (|(a+d)-(b+c)| + |(b+c)-(a+d)|)

You will get an intuition to find all N choose 2 sum and store in the array and call the above function to solve it but it will be wrong.

So, we will first find all N choose 2 sum and store them in an array.

Let us assume our original array was A, then

For i=1 to N: For j = i+1 to N: New_Array.Insert(A[i] + A[j])

What will be wrong in calling Function1(New_Array) ?

Lets go by an example 1 2 3 4.

We will be calling |(1+2) - (1+3)| in some stage, which was not required by specialsum definition.

So, How to eliminate those cases ?

|(a+b)-(a+c)| = |b-c| will be coming exactly N-2 times. [ Reason: There will be N-2 different indices for selection of a ]

Hence our answer will be Function1(New_Array) - (N-2)*Function1(A)