小C的翻转难题

小 C 喜欢数组，尤其是魅力的数组。

对于一个长为 $n$ 的数组 $a$（下标 $1 \sim n$），小 C 定义其魅力值为：

$$
\sum\limits_{i = 1}^{n - 1} \mid a[i + 1] - a[i] \mid
$$

现在小 C 手上有一个长为 $n$ 的数组，但是他仍觉得这个数组不够有魅力。他希望选择这个数组的任意**连续**子数组 ($[a_i, a_{i + 1}, \dots, a_j]$) 并对其进行至多一次翻转（可以不操作）从而最大化数组的魅力值。于是他找到了你，希望你能求出最大的数组魅力值是多少？

第一行输入 $T$，代表共有 $T$ 组数据。

每组数据包含两行：

第一行输入 $n$，代表数组的长度。
第二行输入 $n$ 个用空格隔开的数，第 $i$ 个数代表 $a[i]$，其范围为 $[-10^9, 10^9]$，代表小 C 手上的数组 $a$。

保证所有数据满足 $ \sum n \leq 500000 $

输出共 $T$ 行，每行包含一个整数，代表该组样例的答案。

1
5
2 3 1 5 4

10

[hint] 样例说明：对于数组 $[2,3,1,5,4]$，可将子数组 $[3,1,5]$ 翻转得到 $[2,5,1,3,4]$，此时数组魅力值为 10。

由于输入数据量较大，建议使用 scanf, printf 以代替 cin, cout。 [\hint]

杭州电子科技大学计算机学院Debug杯程序设计竞赛