在他的 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$$$。
输出
对于每个测试用例,输出一个实数 - 最小值 所用时间.
示例
输入复制
354 15 1 7 932 4 8611 13 17 19 23 29
输出复制
11212
注意
对于第一个测试用例,从 $$$[4, 15, 1, 7, 9]$$$ 中删除的一个最佳索引是 $$$k = 2$$$。该数组变为 $$$[4, 1, 7, 9]$$$ 并且 所用时间 是 $$$11$$$。对于第二个测试用例,要删除的最佳索引是 $$$k = 3$$$。