C. Спортивный фестиваль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Студенческий совет готовится к эстафете на спортивном фестивале.

Совет состоит из $$$n$$$ членов. Они будут бегать один за другим в забеге, скорость члена $$$i$$$ равна $$$s_i$$$. Расхождение $$$d_i$$$ $$$i$$$-го этапа — разница между максимальной и минимальной скоростью бега среди первых $$$i$$$ членов, которые участвовали в забеге. Формально, если $$$a_i$$$ обозначает скорость $$$i$$$-го участника, участвовавшего в забеге, то $$$d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_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$$$)  — скорости членов совета.

Выходные данные

Выведите единственное целое число  — минимально возможное значение $$$d_1 + d_2 + \dots + d_n$$$ после выбора порядка, в котором будут бежать члены совета.

Примеры
Входные данные
3
3 1 2
Выходные данные
3
Входные данные
1
5
Выходные данные
0
Входные данные
6
1 6 3 3 6 3
Выходные данные
11
Входные данные
6
104 943872923 6589 889921234 1000000000 69
Выходные данные
2833800505
Примечание

В первом примере, мы можем выбрать, чтобы третий член бежал первым, затем первый, и, наконец, второй. Таким образом, $$$a_1 = 2$$$, $$$a_2 = 3$$$, а $$$a_3 = 1$$$. Тогда получаем:

  • $$$d_1 = \max(2) - \min(2) = 2 - 2 = 0$$$.
  • $$$d_2 = \max(2, 3) - \min(2, 3) = 3 - 2 = 1$$$.
  • $$$d_3 = \max(2, 3, 1) - \min(2, 3, 1) = 3 - 1 = 2$$$.

Полученная сумма равна $$$d_1 + d_2 + d_3 = 0 + 1 + 2 = 3$$$. Можно показать, что меньшего значения добиться невозможно.

Во втором примере единственная возможная перестановка дает $$$d_1 = 0$$$, поэтому минимально возможный результат равен $$$0$$$.