#P1509C. The Sports Festival
-
ID: 2313
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 6
Uploaded By:
Hydro
Tags> The Sports Festival
Description
The student council is preparing for the relay race at the sports festival.
The council consists of $n$ members. They will run one after the other in the race, the speed of member $i$ is $s_i$. The discrepancy $d_i$ of the $i$-th stage is the difference between the maximum and the minimum running speed among the first $i$ members who ran. Formally, if $a_i$ denotes the speed of the $i$-th member who participated in the race, then $d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_i)$.
You want to minimize the sum of the discrepancies $d_1 + d_2 + \dots + d_n$. To do this, you are allowed to change the order in which the members run. What is the minimum possible sum that can be achieved?
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.
Print a single integer — the minimum possible value of $d_1 + d_2 + \dots + d_n$ after choosing the order of the members.
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.
3
3 1 2
1
5
6
1 6 3 3 6 3
6
104 943872923 6589 889921234 1000000000 69
3
0
11
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$.