题目描述

学生会正在为体育节的接力赛做准备。学生会由 $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$