Студенческий совет готовится к эстафете на спортивном фестивале.
Совет состоит из \(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\). Для этого можно изменить порядок, в котором будут бежать участники. Какова минимально возможная сумма?
Выходные данные
Выведите единственное целое число — минимально возможное значение \(d_1 + d_2 + \dots + d_n\) после выбора порядка, в котором будут бежать члены совета.
Примечание
В первом примере, мы можем выбрать, чтобы третий член бежал первым, затем первый, и, наконец, второй. Таким образом, \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|