故事背景

最后一场招新赛了，lfq不希望学弟学妹爆零，所以出了一道简单题。

题目描述

你被给定一个部分填充的非负整数数组 $a_1$,$a_2$,…,$a_n$​，你只有一次机会将该数组中的任何一个数改为一个整数，使得其差分数组元素之和的绝对值最小。

更正式地，令 b是一个长度为 n−1的数组，使得对于所有 1≤i≤n−1，有 $b_i$=$a_{i+1}$−$a_i$。在所有可能的更改方案中，找到 ∣$b_1$+$b_2$+⋯+$b_{n−1}$∣的最小可能值。

输入格式

输入数据如下：

• 每个测试用例的第一行包含一个整数 n(2≤n≤2⋅$10^5$)。
• 每个测试用例的第二行包含 n个整数，$a_1$​,$a_2$​,…,$a_n$(0≤$a_i$≤$10^6$)。

输出格式

对于每个测试用例：输出b数组绝对值之和的最小可能值

Samples

5
1 2 3 4 5

0

Limitation

1s, 1024KiB for each test case.