CF1453B Suffix Operations

Gildong 有一台有趣的机器，里面有一个包含 $n$ 个整数的数组 $a$。这台机器支持两种操作： 1. 将数组的一个后缀中的所有元素增加 $1$。 2. 将数组的一个后缀中的所有元素减少 $1$。 后缀是数组中包含 $a_n$ 的一个子段（连续元素）。换句话说，对于子段中包含的所有 $a_i$，所有满足 $i \lt j \le n$ 的 $a_j$ 也都必须包含在该子段中。 Gildong 想让 $a$ 的所有元素相等 —— 他总是会使用最少的必要操作次数来实现。为了让他的生活更轻松，在 Gildong 开始使用机器之前，你可以选择将数组中的一个整数更改为任何其他整数。你也可以选择保持数组不变。你的目标是让 Gildong 执行的操作次数最少。在你的帮助下，Gildong 将执行的最少操作次数是多少？ 请注意，即使你更改了数组中的一个整数，也不应该将其算作一次操作，因为这不是 Gildong 执行的。

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

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

在第一个例子中，数组的所有元素已经相等。因此，我们不需要更改任何整数，Gildong 将执行 $0$ 次操作。 在第二个例子中，我们可以将 $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$ 开始的后缀使用 $2$ 次第 $1$ 种操作，使数组变为 $[96,96,96,96]$。 在第四个例子中，我们可以将数组改为 $[-3,-3,-2,1]$。现在 Gildong 需要： - 对从 $a_4$ 开始的后缀使用 $3$ 次第 $2$ 种操作，使数组变为 $[-3,-3,-2,-2]$。 - 对从 $a_3$ 开始的后缀使用一次第 $2$ 种操作，使数组变为 $[-3,-3,-3,-3]$。 由 Qwen3.7-Max 翻译。