Minimize Variation

Rearrange the array, compute the maximum minus the minimum of every non-empty prefix, and add these ranges together. Find the minimum total.

输入格式

The first line contains n (1..2000), and the second line contains n values (1..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

3
3 1 2

输出：

3

样例 2

输入：

1
7

输出：

0

样例 3

输入：

3
1 1 5

输出：

4

样例说明

Example 1: the order 1, 2, 3 has prefix ranges 0, 1, 2, for a total of 3. Example 2: there is only one value, range 0. Example 3: place the two 1s first and then 5, giving ranges 0, 0, 4, for a total of 4.