Orange讨厌下雪

题目描述

根据天气预报，沈阳即将引来一场恐怖的下雪，气温会迅速下降，同时地面会堆满积雪，这给宿舍离教学楼一万米远的Orange通勤带来巨大的挑战，这实在是太令人伤心了。

天气预报表示，接下来的 $n$ 天，每天的地面积雪量为 $a_i$，悲伤的Orange每天都会将它记录下来，如果第 $i$ 天的积雪量大于第 $i - 1$ 天，则说明当天又下雪了，Orange的心情就会下降 $|a_i - a_{i-1}|$，反之，如果第 $i$ 天的积雪量小于第 $i - 1$ 天，则说明当天没有下雪并且积雪融化了部分，Orange的心情就会上升 $|a_i - a_{i-1}|$。Orange在第一天记录积雪量后，心情为 $0$。

由于Orange掌握了神奇的魔法，他可以交换任意两天的积雪量，但这个魔法至多使用一次，请问 $n$ 天后，Orange的心情最大值为多少？

输入格式

输入包含多组测试数据。 第一行为一个整数 $T$，表示测试数据的组数。 对于每组测试数据： 第一行为一个整数 $n$，表示天气预报的天数。 第二行为 $n$ 个整数 $a_i$，表示第 $i$ 天的地面积雪量。

数据范围: $1 \le T,n \le 10^5$ $1 \le a_i \le 10^9$ 保证: $\sum n \le 10^5$

输出格式

对于每组数据，给出答案。

样例 #1

样例输入 #1

2
4
1 7 3 2
5
2 1 7 3 5

样例输出 #1

5
3