CF1509C.The Sports Festival

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?

学生会正在为运动会的接力赛做准备。

学生会由 $n$ 名成员组成。他们将依次参加比赛，第 $i$ 名成员的速度为 $s_i$。第 $i$ 个赛段的差异值 $d_i$ 定义为前 $i$ 个参赛成员速度的最大值与最小值之差。形式化地，若 $a_i$ 表示第 $i$ 个参赛成员的速度，则

$$d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_i).$$

你希望最小化所有差异值之和 $d_1 + d_2 + \dots + d_n$。为此，你可以任意调整成员的出场顺序。请问：所能达到的最小可能总和是多少？

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.

第一行包含一个整数 $n$（$1 \le n \le 2000$）——学生会成员的数量。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$）——各成员的跑步速度。

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

输出一个整数——在选定成员顺序后，$d_1 + d_2 + \dots + d_n$ 的最小可能值。

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$.

在第一个测试用例中，我们可以选择让第三位成员先跑，然后是第一位成员，最后是第二位成员。因此有 $a_1 = 2$，$a_2 = 3$，$a_3 = 1$。我们得到：

• $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$。

最终的和为 $d_1 + d_2 + d_3 = 0 + 1 + 2 = 3$。可以证明，无法得到更小的值。

在第二个测试用例中，唯一可能的重排方式给出 $d_1 = 0$，因此可能的最小结果为 $0$。