← 返回题目列表

Codeforces · 2179/B

B. Blackslex 和 淋浴

中文机器翻译题面 查看原题

在他的 IMO 奖牌得主朋友洗了两个小时的澡以便“这周他不必再洗这个”之后,Blackslex 上课要迟到了!

为了去上课,Blackslex 必须按照一定的顺序乘坐拥挤的电梯到达许多楼层。因为他是一名黑客,所以他可以在其他人不知道的情况下跳过一层楼。他的 所用时间 是连续楼层号之间的绝对差之和。找到最小值 所用时间,因为他可以跳到一层。

更正式地说,给定一个包含 $$$n$$$ 整数的数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,您最多可以选择一个索引 $$$k \in \{1, 2, \ldots, n\}$$$ 来擦除,这样总和 $$\sum_{i=1}^{n-2} |b_i - b_{i+1}|$$ 被最小化,其中 $$$b = [a_1, \ldots, a_{k-1}, a_{k+1}, \ldots, a_n]$$$ 是删除元素 $$$a_k$$$ 后的数组。报告最低金额。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 数组的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$)。

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

输出

对于每个测试用例,输出一个实数 - 最小值 所用时间.

示例

输入
复制

3
5
4 15 1 7 9
3
2 4 8
6
11 13 17 19 23 29

输出
复制

11
2
12

注意

对于第一个测试用例,从 $$$[4, 15, 1, 7, 9]$$$ 中删除的一个最佳索引是 $$$k = 2$$$。该数组变为 $$$[4, 1, 7, 9]$$$ 并且 所用时间 是 $$$11$$$。对于第二个测试用例,要删除的最佳索引是 $$$k = 3$$$。