CF2153D.Not Alone

A circular array $b$ of length $m$ is nice if every element has at least one adjacent element$^{\text{∗}}$ that is equal to it. Formally, for every $1\le i\le m$, at least one of the following holds: $b_i = b_{(i+m-2)\bmod m\;+1}$, or $b_i = b_{i\bmod m\;+1}$, where $x \bmod y$ denotes the remainder from dividing $x$ by $y$.

You are given a circular array $a$ of length $n$. In one operation, you may increase or decrease any element of $a$ by $1$. Your task is to determine the minimum number of operations required to make array $a$ nice. More formally, find the minimum value of $\sum_{i=1}^n |b_i - a_i|$ among all nice circular arrays $b$ of length $n$.

$^{\text{∗}}$In a circular array of length $m$:

• For each index $2\le i\le m - 1$, the element at index $i$ is adjacent to the elements at indices $i - 1$ and $i + 1$.
• The element at index $1$ is adjacent to the elements at indices $2$ and $m$.
• The element at index $m$ is adjacent to the elements at indices $m - 1$ and $1$.

长度为 $m$ 的环形数组 $b$ 被称为“优美的”（nice），当且仅当其中每个元素至少有一个相邻元素$^{\text{∗}}$与其相等。形式化地，对每个 $1\le i\le m$，以下至少一个条件成立：

$$b_i = b_{(i+m-2)\bmod m\;+1} \quad \text{或} \quad b_i = b_{i\bmod m\;+1},$$

其中 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。

你被给定一个长度为 $n$ 的环形数组 $a$。每次操作中，你可以将 $a$ 的任意一个元素增加或减少 $1$。你的任务是确定使数组 $a$ 变为优美的所需的最少操作次数。更准确地说，求所有长度为 $n$ 的优美环形数组 $b$ 中，$\sum_{i=1}^n |b_i - a_i|$ 的最小值。

$^{\text{∗}}$ 在长度为 $m$ 的环形数组中：

• 对每个下标 $2\le i\le m - 1$，位于下标 $i$ 处的元素与下标 $i - 1$ 和 $i + 1$ 处的元素相邻；
• 位于下标 $1$ 处的元素与下标 $2$ 和 $m$ 处的元素相邻；
• 位于下标 $m$ 处的元素与下标 $m - 1$ 和 $1$ 处的元素相邻。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3\le n\le 2\cdot 10^5$) — the length of the circular array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1\le a_i\le 10^9$) — the elements of the circular array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output a single integer representing the minimum number of operations required to make array $a$ nice.

对于每个测试用例，输出一个整数，表示使数组 $a$ 变为“好”的所需最少操作次数。

In the first test case, all elements of $a$ are equal. Therefore, the circular array $a$ is already nice and no operations are required.

In the second test case, we can perform the following sequence of operations:

• Increase $a_1$ by $1$. Now, $a=[3, 100, 99, 3]$.
• Decrease $a_2$ by $1$. Now, $a=[3, 99, 99, 3]$.

After these operations, every element has at least one adjacent element with the same value:

• $a_1$ is equal to $a_4$.
• $a_2$ is equal to $a_3$.
• $a_3$ is equal to $a_2$.
• $a_4$ is equal to $a_1$.

In the third test case, the circular array $a$ can become nice by decreasing $a_4$ four times. This results in $a = [2, 2, 5, 5, 5]$ which is nice as every element has at least one adjacent element with the same value.

在第一个测试用例中，数组 $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_4$ 减少四次，循环数组 $a$ 可变为“优美的”。结果为 $a = [2, 2, 5, 5, 5]$，该数组是“优美的”，因为每个元素至少有一个相邻元素与其值相等。