CFCF2153D.Not Alone

一个长度为 $m$ 的环形数组 $b$ 被称为“优美”，如果其中每个元素至少有一个相邻元素等于它。形式化地，对于每个 $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$ 的余数。

现在给定一个长度为 $n$ 的环形数组 $a$。你可以进行如下操作：每次将 $a$ 中的任意一个元素加 $1$ 或减 $1$。你的任务是计算最少需要多少次操作，才能使数组 $a$ 变成“优美”的环形数组。更正式地说，求在所有优美环形数组 $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$ 个元素。

输入包含多组测试用例。第一行为测试用例数 $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$ 变为优美的环形数组。

在第一个测试用例中，$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$ 连续减 $4$，此时 $a = [2, 2, 5, 5, 5]$，该数组为优美数组，因为每个元素都有至少一个相邻元素等于自己。