A16659 | 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$ 变为优美的环形数组。