How do I calculate team score

Problem Statement

There are N students in a school with different capabilities.

Sports teacher wants to form some teams of these students following the rule: Each team can have either 1 or 2 students.

Capability score of each team is the sum of the capabilities of each student in that particular team.

Since the teacher believes in equality, he wants to form the teams such that the difference between capability scores of the teams with highest capability score and the lowest capability score should be minimized.

Note: The teacher can form any number of teams

 

Constraints

1 ≤ N ≤ 5*10^3

-10^9 ≤ Ci ≤ 10^9

 

Input Format

The first line contains an integer N denoting number of students.

Second line contains N integers, separated by space, denoting capabilities of each student (Ci).

 

Output Format

A single integer denoting the difference between maximum capability score and minimum capability scores among all teams.

 

Sample Input

3

2 6 3

 

Sample Output

1

 

Explanation of Sample

Most optimal way is to form two teams of [2, 3] and [6].
Here, the capability scores of two teams will be 5 and 6 respectively.
Hence, the team with maximum score = 6 and the team with lowest score = 5.
Difference = 1
This is the minimal difference that we can achieve in this case.

 

Things to Note for the Candidate

You can use your own IDE like Visual Studio Code, Eclipse or any other IDE that you are comfortable with to build your solution code.
The IDE provided on the platform is purely for submission. Avoid using the IDE for coding out the solution.
Test against any custom input in your own IDE. In the IDE provided on the platform, you cannot pass custom test cases and see the output. 
Use standard input and standard output in your program for the IDE to run the test cases smoothly against your code. We are giving a sample problem statement along with a solution that will pass the test cases in the IDE. - Sample Problem Statement  (Right Click and Open in New Tab to view.)

3x3 matrix
X = [[12,7,3],
    [4 ,5,6],
    [7 ,8,9]]
# 3x4 matrix
Y = [[5,8,1,2],
    [6,7,3,0],
    [4,5,9,1]]
# result is 3x4
result = [[0,0,0,0],
         [0,0,0,0],
         [0,0,0,0]]

# iterate through rows of X
for i in range(len(X)):
   # iterate through columns of Y
   for j in range(len(Y[0])):
       # iterate through rows of Y
       for k in range(len(Y)):
           result[i][j] += X[i][k] * Y[k][j]

for r in result:
   print(r)