Исследуя джунгли, вы наткнулись на редкого орангутана с галстуком-бабочкой! Вы пожали орангутану руку и предложили ему немного еды и воды. В ответ...
Орангутан подарил вам массив \(a\) длины \(n\). Используя \(a\), вы построили два массива \(b\) и \(c\), каждый из которых будет содержать \(n\) элементов, следующим образом:
- \(b_i = \min(a_1, a_2, \ldots, a_i)\) для каждого \(1 \leq i \leq n\).
- \(c_i = \max(a_1, a_2, \ldots, a_i)\) для каждого \(1 \leq i \leq n\).
Определим счёт массива \(a\) как \(\sum_{i=1}^n c_i - b_i\) (т.е. сумму \(c_i - b_i\) по всем \(1 \leq i \leq n\)). Прежде чем вычислять счёт, вы можете переставить элементы \(a\) в любом порядке.
Найдите максимальный счёт, который вы можете получить, если оптимально переставите элементы \(a\).
Выходные данные
Для каждого набора входных данных выведите максимальный счёт, который вы можете получить.
Примечание
В первом наборе входных данных нет другого способа переставить элементы \(a\). Таким образом, \(b = [69]\) и \(c = [69]\). Единственный возможный счёт — \(69 - 69 = 0\).
Во втором наборе входных данных можно переставить элементы \(a\) так: \([7, 5, 6]\). Тогда \(b = [7, 5, 5]\) и \(c = [7, 7, 7]\). Счёт в этом случае будет равен \((7 - 7) + (7 - 5) + (7 - 5) = 4\). Можно показать, что это максимально возможный счёт.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
69
3
7 6 5
5
1 1 1 2 2
|
0
4
4
|