学生会正在准备体育祭的接力赛。
理事会由 $$$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$$$ 的最小可能值。
示例
输入 #1
3 3 1 2
输出 #1
3
输入 #2
1 5
输出 #2
0
输入 #3
6 1 6 3 3 6 3
输出 #3
11
输入#4
6 104 943872923 6589 889921234 1000000000 69
输出#4
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$$$。