Sports Festival

Problem Description

The student union is preparing for the relay race of the sports festival. The student union consists of $n$ members who will run one by one in the race. The $i$-th person has speed $s_i$. The $i$-th leg of the relay produces a difference value $d_i$, which equals the difference between the maximum and minimum speeds among the first $i$ participants — that is, if we denote the speed of the $i$-th participant as $a_i$, then $d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_i)$.

You may arrange the running order of the participants arbitrarily. Each person participates exactly once and everyone must participate. Find the minimum possible value of $d_1 + d_2 + \dots + d_n$.

Input Format

The first line contains a positive integer $n$. The second line contains $n$ integers representing $a_i$.

Output Format

Output one integer, the answer.

Sample Input

3
3 1 2

Sample Output

3

Constraints

$1 \le n \le 2000$,

$1 \le s_i \le 10^9$