B. Суффиксные операции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Gildong есть интересная машина, которая оперирует над массивом $$$a$$$ из $$$n$$$ целых чисел. Машина умеет выполнять операции двух типов:

  1. Увеличить все элементы на суффиксе массива на $$$1$$$.
  2. Уменьшить все элементы на суффиксе массива на $$$1$$$.

Суффикс это подотрезок (последовательных элементов) массива, содержащий $$$a_n$$$. Иначе говоря, для всех $$$i$$$, что $$$a_i$$$ включен в отрезок, все $$$a_j$$$, что $$$i \lt j \le n$$$ тоже должны быть включены в отрезок.

Gildong хочет сделать все элементы в $$$a$$$ равными — он всегда будет это делать минимальным возможным числом операций. Чтобы облегчить ему жизнь, перед тем, как Gildong начнет использовать машину, у вас есть возможность заменить любой один элемент массива на любое целое число. Вам разрешается оставить массив нетронутым. Вы хотите минимизировать число операций, которое совершит Gildong. С вашей помощью, какое минимальное число операций совершит Gildong?

Обратите внимание, что даже если вы измените одно число в массиве, вы не должны считать это как одну из операций, потому что Gildong ее не совершал.

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

Каждый тест состоит из одного или нескольких наборов входных данных. В первой строке записано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 1000$$$).

Каждый набор входных данных состоит из двух строк. В первой строке каждого набора входных записано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел. $$$i$$$-е из них это $$$a_i$$$ ($$$-5 \cdot 10^8 \le a_i \le 5 \cdot 10^8$$$).

Гарантируется, что сумма $$$n$$$ по всем наборах входных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество операций, которое должен совершить Gildong, чтобы сделать все элементы массива равными.

Пример
Входные данные
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
Примечание

В первом наборе входных данных все элементы массива уже одинаковы. Таким образом, вам не требуется совершать никаких операций, и 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]$$$.