The Sports Festival

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$)  — the number of members of the student council.

The second line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$)  – the running speeds of the members.

Output:

Print a single integer  — the minimum possible value of $$$d_1 + d_2 + \dots + d_n$$$ after choosing the order of the members.

Sample Input:

3
3 1 2

Sample Output:

3

Sample Input:

1
5

Sample Output:

0

Sample Input:

6
1 6 3 3 6 3

Sample Output:

11

Sample Input:

6
104 943872923 6589 889921234 1000000000 69

Sample Output:

2833800505

Note:

In the first test case, we may choose to make the third member run first, followed by the first member, and finally the second. Thus $$$a_1 = 2$$$, $$$a_2 = 3$$$, and $$$a_3 = 1$$$. We have:

• $$$d_1 = \max(2) - \min(2) = 2 - 2 = 0$$$.
• $$$d_2 = \max(2, 3) - \min(2, 3) = 3 - 2 = 1$$$.
• $$$d_3 = \max(2, 3, 1) - \min(2, 3, 1) = 3 - 1 = 2$$$.

The resulting sum is $$$d_1 + d_2 + d_3 = 0 + 1 + 2 = 3$$$. It can be shown that it is impossible to achieve a smaller value.

In the second test case, the only possible rearrangement gives $$$d_1 = 0$$$, so the minimum possible result is $$$0$$$.