Саша нашел массив \(a\), состоящий из \(n\) целых чисел, и попросил вас раскрасить элементы.
Вы должны раскрасить каждый элемент массива. Вы можете использовать столько цветов, сколько захотите, но каждый элемент должен быть окрашен ровно в один цвет, и для каждого цвета должен быть хотя бы один элемент этого цвета.
Стоимость одного цвета — это значение \(\max(S) - \min(S)\), где \(S\) — последовательность элементов этого цвета. Стоимость всей раскраски — это сумма стоимостей по всем цветам.
Например, предположим, что у вас есть массив \(a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]\), вы раскрасили его элементы в два цвета следующим образом: элементы на позициях \(1\), \(2\) и \(5\) имеют цвет \(1\); элементы на позициях \(3\) и \(4\) имеют цвет \(2\). Тогда:
- Стоимость цвета \(1\) составляет \(\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4\);
- Стоимость цвета \(2\) равна \(\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3\);
- Общая стоимость раскраски равна \(7\).
Для данного массива \(a\) вы должны рассчитать максимальную возможную стоимость раскраски.
Выходные данные
Для каждого набора входных данных выведите максимальную возможную стоимость раскраски в отдельной строке.
Примечание
В первом примере одной из оптимальных раскрасок является \([\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]\). Ответ для неё равен \((5 - 1) + (6 - 3) = 7\).
Во втором примере единственной возможной раскраской является \([\color{blue}{5}]\), для которой ответ равен \(5 - 5 = 0\).
В третьем примере оптимальной окраской является \([\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]\), для которой ответ равен \((9 - 1) + (6 - 3) = 11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3
|
7
0
11
23
0
5
|