Gildong 有一台有趣的机器,它有一个数组 $$$a$$$ 和 $$$n$$$ 整数。本机支持两种操作:
1. 将数组后缀的所有元素增加$$$1$$$。
2. 将数组后缀的所有元素减少$$$1$$$。
后缀是包含 $$$a_n$$$ 的数组的子段(连续元素)。换句话说,对于所有 $$$i$$$(其中 $$$a_i$$$ 包含在子段中),所有 $$$a_j$$$(其中 $$$i \lt j \le n$$$)也必须包含在子段中。
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 必须执行的最小操作数才能使数组的所有元素相等。
示例
输入 #1
7 2 1 1 3 -1 0 2 4 99 96 97 95 4 -3 -5 -2 1 6 1 4 3 2 4 1 5 5 0 0 0 5 9 -367741579 319422997 -415264583 -125558838 -300860379 420848004 294512916 -383235489 425814447
输出 #1
0 1 3 4 6 5 2847372102
注意
在第一种情况下,数组的所有元素都已经相等。因此,我们不改变任何整数,Gildong 将执行零运算。
第二种情况,我们可以将$$$a_3$$$设置为$$$0$$$,这样数组就变成了$$$[-1,0,0]$$$。现在 Gildong 可以对从 $$$a_2$$$ 开始的后缀使用一次 $$$2$$$-nd 操作,这意味着 $$$a_2$$$ 和 $$$a_3$$$ 减少 $$$1$$$,使数组的所有元素为 $$$-1$$$。
第三种情况,我们可以将$$$a_1$$$设置为$$$96$$$,这样数组就变成了$$$[96,96,97,95]$$$。现在吉尔东需要:
- 对从 $$$a_3$$$ 开始的后缀使用 $$$2$$$-nd 操作一次,生成数组 $$$[96,96,96,94]$$$。
- 对从 $$$a_4$$$ $$$2$$$ 开始的后缀使用 $$$1$$$-st 操作,生成数组 $$$[96,96,96,96]$$$。
第四种情况,我们可以将数组改为$$$[-3,-3,-2,1]$$$。现在吉尔东需要:
- 对从 $$$a_4$$$ $$$3$$$ 开始的后缀使用 $$$2$$$-nd 操作,生成数组 $$$[-3,-3,-2,-2]$$$。
- 对从 $$$a_3$$$ 开始的后缀使用 $$$2$$$-nd 操作一次,生成数组 $$$[-3,-3,-3,-3]$$$。