题目描述

有 $n$ 名参赛者要依次参加接力赛，第 $i$ 名参赛者的速度为 $s_i$。你可以任意决定他们的出场顺序。

设重排后的速度序列为 $a_1,a_2,\dots,a_n$。第 $i$ 个阶段的不协调度定义为前 $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$），表示各参赛者的速度。

输出格式

输出一个整数，表示最小可能的不协调度总和。

样例

样例 1

输入：

3
3 1 2

输出：

3

样例 2

输入：

1
5

输出：

0

样例 3

输入：

6
1 6 3 3 6 3

输出：

11

样例 4

输入：

6
104 943872923 6589 889921234 1000000000 69

输出：

2833800505