题目描述
学生会正在为体育节的接力赛做准备。学生会由 $n$个成员组成,他们将在比赛中一个一个地跑,第 $i$ 个人的速度是 $s_i$,第 $i$次接力会产生一个差异值 $d_i$,它的值是前 $i$个参与接力赛的人的速度最大值与最小值的差,也就是说,我们假设第 $i$个参与比赛的人的速度是 $a_i$,那么 $d_i = max(a_1, a_2,..., a_i) - min(a_1, a_2,..., a_i)$。现在你可以任意安排参加比赛的人的顺序,一个人只能参与一次,且每个人都必须参与,请你求出 $d_1 + d_2 + ... + d_n$的最小值。
输入格式
第一行输入一个正整数n,第二行输入 $i$个整数代表 $a_i$
输出格式
输出一个整数,代表答案
样例输入
3
3 1 2
样例输出
3
数据规模
$1 \leq n \leq 2000$, $1 \leq s_i \leq 1e9$