题目描述

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

学生会由 $n$ 名成员组成。他们将在比赛中依次跑步，第 $i$ 位成员的速度为 $s_i$。

比赛一共分 $n$ 个阶段，每个阶段都会派出一名未参赛的成员参赛。第 $i$ 阶段的 差异值 $d_i$ 是前 $i$ 名参赛成员中最大跑步速度和最小跑步速度之间的差异。具体来说，如果 $a_i$ 表示参加比赛的第 $i$ 名成员的速度，则 $d_i = \max(a_1, a_2, \ldots, a_i) - \min(a_1, a_2, \ldots, a_i)$。

你希望使 $n$ 个阶段的差异值总和（即 $d_1 + d_2 + \ldots + d_n$）最小。为了实现这一目标，你可以改变成员跑步的顺序。

求：能够达到的差异值总和最小是多少？

输入格式

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

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

输出格式

输出一个整数 _ 调整成员参赛的顺序后的最小差异值总和 $d_1 + d_2 + \ldots + 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$。