D. Не одинок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Циклический массив $$$b$$$ длины $$$m$$$ является приятным, если каждый элемент имеет хотя бы один соседний элемент$$$^{\text{∗}}$$$, равный ему. Формально, для каждого $$$1\le i\le m$$$ выполняется хотя бы одно из следующих условий: $$$b_i = b_{(i+m-2)\bmod m\;+1}$$$ или $$$b_i = b_{i\bmod m\;+1}$$$, где $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.

Вам дан циклический массив $$$a$$$ длины $$$n$$$. За одну операцию вы можете увеличить или уменьшить любой элемент массива $$$a$$$ на $$$1$$$. Ваша задача — определить минимальное количество операций, необходимых для того, чтобы сделать массив $$$a$$$ приятным. Более формально, найдите минимальное значение $$$\sum_{i=1}^n |b_i - a_i|$$$ среди всех приятных циклических массивов $$$b$$$ длины $$$n$$$.

$$$^{\text{∗}}$$$В циклическом массиве длины $$$m$$$:

  • Для каждого индекса $$$2\le i\le m - 1$$$ элемент с индексом $$$i$$$ соседствует с элементами с индексами $$$i - 1$$$ и $$$i + 1$$$.
  • Элемент с индексом $$$1$$$ соседствует с элементами с индексами $$$2$$$ и $$$m$$$.
  • Элемент с индексом $$$m$$$ соседствует с элементами с индексами $$$m - 1$$$ и $$$1$$$.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3\le n\le 2\cdot 10^5$$$) — длина циклического массива $$$a$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — элементы циклического массива $$$a$$$.

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

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

Для каждого набора входных данных выведите одно целое число, обозначающее минимальное количество операций, необходимых для того, чтобы сделать массив $$$a$$$ приятным.

Пример
Входные данные
4
5
1 1 1 1 1
4
2 100 99 3
5
2 2 5 9 5
6
1 1 1 2 1 2
Выходные данные
0
2
4
1
Примечание

В первом наборе входных данных все элементы массива $$$a$$$ равны. Поэтому циклический массив $$$a$$$ уже приятен, и операции не требуются.

Во втором наборе входных данных мы можем выполнить следующую последовательность операций:

  • Увеличить $$$a_1$$$ на $$$1$$$. Теперь $$$a=[3, 100, 99, 3]$$$.
  • Уменьшить $$$a_2$$$ на $$$1$$$. Теперь $$$a=[3, 99, 99, 3]$$$.

После этих операций каждый элемент имеет хотя бы один соседний элемент с таким же значением:

  • $$$a_1$$$ равен $$$a_4$$$.
  • $$$a_2$$$ равен $$$a_3$$$.
  • $$$a_3$$$ равен $$$a_2$$$.
  • $$$a_4$$$ равен $$$a_1$$$.

В третьем наборе входных данных циклический массив $$$a$$$ может стать приятным, если уменьшить $$$a_4$$$ четыре раза. В результате получится $$$a = [2, 2, 5, 5, 5]$$$, который является приятным, так как каждый элемент имеет хотя бы один соседний элемент с таким же значением.