You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

学生会共有 $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$ 的最小可能值。

3
3 1 2

3

1
5

0

6
1 6 3 3 6 3

11

6
104 943872923 6589 889921234 1000000000 69

2833800505

说明/提示

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