У Gildong есть интересная машина, которая оперирует над массивом \(a\) из \(n\) целых чисел. Машина умеет выполнять операции двух типов:
- Увеличить все элементы на суффиксе массива на \(1\).
- Уменьшить все элементы на суффиксе массива на \(1\).
Суффикс это подотрезок (последовательных элементов) массива, содержащий \(a_n\). Иначе говоря, для всех \(i\), что \(a_i\) включен в отрезок, все \(a_j\), что \(i \lt j \le n\) тоже должны быть включены в отрезок.
Gildong хочет сделать все элементы в \(a\) равными — он всегда будет это делать минимальным возможным числом операций. Чтобы облегчить ему жизнь, перед тем, как Gildong начнет использовать машину, у вас есть возможность заменить любой один элемент массива на любое целое число. Вам разрешается оставить массив нетронутым. Вы хотите минимизировать число операций, которое совершит Gildong. С вашей помощью, какое минимальное число операций совершит Gildong?
Обратите внимание, что даже если вы измените одно число в массиве, вы не должны считать это как одну из операций, потому что Gildong ее не совершал.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, которое должен совершить Gildong, чтобы сделать все элементы массива равными.
Примечание
В первом наборе входных данных все элементы массива уже одинаковы. Таким образом, вам не требуется совершать никаких операций, и Gildong совершит ноль операций.
Во втором наборе входных данных мы можем сделать \(a_3\) равным \(0\), и массив превратится в \([-1,0,0]\). После этого Gildong может совершить \(2\)-ю операцию один раз на суффиксе, начинающимся с \(a_2\), что уменьшит \(a_2\) и \(a_3\) на \(1\), превратив все элементы массива в \(-1\).
В третьем наборе входных данных можно сделать \(a_1\) равным \(96\), так что массив превратится в \([96,96,97,95]\). После этого Gildong должен:
- Использовать \(2\)-ю операцию на суффиксе, который начинается с \(a_3\), один раз, превратив массив в \([96,96,96,94]\).
- Использовать \(1\)-ю операцию на суффиксе, который начинается с \(a_4\), \(2\) раза, превратив массив в \([96,96,96,96]\).
В четвертом примере можно заменить массив на \([-3,-3,-2,1]\). Затем Gildong должен:
- Использовать \(2\)-ю операцию на суффиксе, который начинается с \(a_4\), \(3\) раза, превратив массив в \([-3,-3,-2,-2]\).
- Испоьзовать \(2\)-ю операцию на суффиксе, который начинается с \(a_3\), один раз, превратив массив в \([-3,-3,-3,-3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2
1 1
3
-1 0 2
4
99 96 97 95
4
-3 -5 -2 1
6
1 4 3 2 4 1
5
5 0 0 0 5
9
-367741579 319422997 -415264583 -125558838 -300860379 420848004 294512916 -383235489 425814447
|
0
1
3
4
6
5
2847372102
|