题目描述

给定长度为 $n$ 的序列 $s$，你可以任意改变序列 $s$ 的顺序。

求

$$\sum_{i=1}^{n}\left(\max_{j=1}^{i} s_j - \min_{j=1}^{i} s_j\right)$$

的最小值。

输入格式

第一行一个整数 $n$，代表序列的长度。

第二行 $n$ 个整数，分别为 $s_1, s_2, s_3, \dots, s_n$。

输出格式

输出一个整数，为

$$\sum_{i=1}^{n}\left(\max_{j=1}^{i} s_j - \min_{j=1}^{i} s_j\right)$$

的最小值。

样例 #1

样例输入 #1

3
3 1 2

样例输出 #1

3

样例 #2

样例输入 #2

1
5

样例输出 #2

0

样例 #3

样例输入 #3

6
1 6 3 3 6 3

样例输出 #3

11

样例 #4

样例输入 #4

6
104 943872923 6589 889921234 1000000000 69

样例输出 #4

2833800505

数据范围

对于 $20\%$ 的数据保证，$n \le 12$。

对于 $50\%$ 的数据保证，$n \le 300$。

对于所有数据保证，$1 \le n \le 2000$，$1 \le s_i \le 10^9$。