CF1509C The Sports Festival

学生会正在为运动会的接力赛做准备。 学生会共有 $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$。为此，你可以改变成员的出场顺序。请问最小可能的总和是多少？

第一行包含一个整数 $n$（$1 \le n \le 2000$），表示学生会成员人数。 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$），表示各成员的奔跑速度。

输出一个整数，表示通过选择成员出场顺序后，$d_1 + d_2 + \dots + d_n$ 的最小可能值。

在第一个测试样例中，我们可以选择让第三位成员先跑，然后是第一位成员，最后是第二位成员。这样 $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$。 由 ChatGPT 4.1 翻译