Description

给定一个长为 $n$ 的正整数序列 $a$，序列的价值定义为 $\sum_{i=1}^{n-1} |a_{i+1}-a_i|$。

现在你需要对序列的一个非空前缀进行翻转，再对序列的一个非空后缀进行翻转，使得序列的价值最大。

称 $p$ 为 $a$ 的一个前缀，当且仅当 $p$ 可以通过 $a$ 从后往前依次删除若干元素得到，称 $s$ 为 $a$ 的一个后缀，当且仅当 $p$ 可以通过 $a$ 从前往后依次删除若干元素得到。例如，对于 $a=\{1,2,3,4,5\}$，则 $\{1,2,3\},\{1\},\{1,2,3,4,5\}$ 均为 $a$ 的前缀，而 $\{2,3,4\},\{1,3,4\}$ 不是 $a$ 的前缀；$\{4,5\},\{5\},\{1,2,3,4,5\}$ 均为 $a$ 的后缀，而 $\{2,3,5\},\{3,4\}$ 不是 $a$ 的后缀。

翻转操作按如下方式进行：

1. 对于要翻转的区间 $[l,r]$，定义 $b_i=a_{r-i+1}$，其中 $1\le i\le r-l+1$；
2. 用得到的 $b$ 序列替换 $a$ 序列中 $[l,r]$ 位置的元素。

例如，对于 $a=\{1,2,3,4,5\}$，翻转区间为 $[1,3]$，得到的翻转后数组为 $a=\{3,2,1,4,5\}$。

Input

第一行一个正整数 $T$（$1\le T\le 10^5$），表示共有 $T$ 组数据。

对于每组数据，第一行一个正整数 $n$（$1\le n\le 10^5$），表示序列的长度。

第二行 $n$ 个正整数 $a_i$（$1\le a_i\le 10^9$），表示给定的序列。

对于所有数据，满足 $\sum n \le 10^6$。

Output

对于每组数据，输出一行一个整数表示序列两次翻转后最大的价值。

Samples

5
1
1
2
3 7
3
10 2 7
5
1 5 3 8 7
8
9 7 3 6 8 5 4 6

0
4
13
19
21

Resources

The 23rd UESTC Programming Contest Preliminary