长度为 $$$m$$$ 的循环数组 $$$b$$$ 为 不错 如果每个元素至少有一个与其相等的相邻元素$$$^{\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$$$ 除以 $$$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$$$ 处的元素相邻。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 良好所需的最少操作数。
示例
输入复制
451 1 1 1 142 100 99 352 2 5 9 561 1 1 2 1 2
输出复制
0241
注意
在第一个测试用例中,$$$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]$$$,这很好,因为每个元素至少有一个具有相同值的相邻元素。