CF1453B.Suffix Operations

Gildong has an interesting machine that has an array $a$ with $n$ integers. The machine supports two kinds of operations:

1. Increase all elements of a suffix of the array by $1$.
2. Decrease all elements of a suffix of the array by $1$.

A suffix is a subsegment (contiguous elements) of the array that contains $a_n$. In other words, for all $i$ where $a_i$ is included in the subsegment, all $a_j$'s where $i \lt j \le n$ must also be included in the subsegment.

Gildong wants to make all elements of $a$ equal — he will always do so using the minimum number of operations necessary. To make his life even easier, before Gildong starts using the machine, you have the option of changing one of the integers in the array to any other integer. You are allowed to leave the array unchanged. You want to minimize the number of operations Gildong performs. With your help, what is the minimum number of operations Gildong will perform?

Note that even if you change one of the integers in the array, you should not count that as one of the operations because Gildong did not perform it.

吉隆拥有一台有趣的机器，该机器维护一个包含 $n$ 个整数的数组 $a$。这台机器支持两种操作：

1. 将数组某个后缀的所有元素增加 $1$；
2. 将数组某个后缀的所有元素减少 $1$。

所谓“后缀”，是指包含 $a_n$ 的一个子段（即连续的一段元素）。换言之，若某个下标 $i$ 对应的元素 $a_i$ 属于该子段，则对所有满足 $i < j \le n$ 的下标 $j$，其对应元素 $a_j$ 也必须属于该子段。

吉隆希望将数组 $a$ 的所有元素变为相等——他总会以最少的操作次数达成这一目标。为了让他的任务更加轻松，在吉隆开始使用机器之前，你可以选择将数组中的某一个整数修改为任意其他整数（你也可以选择不作任何修改）。你的目标是使吉隆最终执行的操作次数尽可能少。在你的帮助下，吉隆最少需要执行多少次操作？

注意：即使你修改了数组中的某个整数，该修改不计入操作次数，因为这不是吉隆执行的操作。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$).

Each test case contains two lines. The first line of each test case consists of an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of elements of the array $a$.

The second line of each test case contains $n$ integers. The $i$-th integer is $a_i$ ($-5 \cdot 10^8 \le a_i \le 5 \cdot 10^8$).

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

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。

每个测试用例包含两行。每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 表示数组 $a$ 的元素个数。

每个测试用例的第二行包含 $n$ 个整数，其中第 $i$ 个整数为 $a_i$（$-5 \cdot 10^8 \le a_i \le 5 \cdot 10^8$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the minimum number of operations Gildong has to perform in order to make all elements of the array equal.

对于每个测试用例，输出一个整数——Gildong 为使数组所有元素相等所需执行的最少操作次数。

In the first case, all elements of the array are already equal. Therefore, we do not change any integer and Gildong will perform zero operations.

In the second case, we can set $a_3$ to be $0$, so that the array becomes $[-1,0,0]$. Now Gildong can use the $2$-nd operation once on the suffix starting at $a_2$, which means $a_2$ and $a_3$ are decreased by $1$, making all elements of the array $-1$.

In the third case, we can set $a_1$ to $96$, so that the array becomes $[96,96,97,95]$. Now Gildong needs to:

• Use the $2$-nd operation on the suffix starting at $a_3$ once, making the array $[96,96,96,94]$.
• Use the $1$-st operation on the suffix starting at $a_4$ $2$ times, making the array $[96,96,96,96]$.

In the fourth case, we can change the array into $[-3,-3,-2,1]$. Now Gildong needs to:

• Use the $2$-nd operation on the suffix starting at $a_4$ $3$ times, making the array $[-3,-3,-2,-2]$.
• Use the $2$-nd operation on the suffix starting at $a_3$ once, making the array $[-3,-3,-3,-3]$.

在第一种情况下，数组的所有元素已经相等。因此，我们不修改任何整数，Gildong 将执行零次操作。

在第二种情况下，我们可以将 $a_3$ 设为 $0$，使数组变为 $[-1,0,0]$。此时 Gildong 可以对从 $a_2$ 开始的后缀使用第 $2$ 种操作一次，即 $a_2$ 和 $a_3$ 各减 $1$，从而使数组所有元素变为 $-1$。

在第三种情况下，我们可以将 $a_1$ 设为 $96$，使数组变为 $[96,96,97,95]$。此时 Gildong 需要：

• 对从 $a_3$ 开始的后缀使用一次第 $2$ 种操作，使数组变为 $[96,96,96,94]$；
• 对从 $a_4$ 开始的后缀使用两次第 $1$ 种操作，使数组变为 $[96,96,96,96]$。

在第四种情况下，我们可以将数组改为 $[-3,-3,-2,1]$。此时 Gildong 需要：

• 对从 $a_4$ 开始的后缀使用三次第 $2$ 种操作，使数组变为 $[-3,-3,-2,-2]$；
• 对从 $a_3$ 开始的后缀使用一次第 $2$ 种操作，使数组变为 $[-3,-3,-3,-3]$。