说明

一场连续 $n$ 天的大雨即将席卷而来，其中第 $i$ 天雨势的大小为 $a_i$。Soyo不喜欢雨天，她期待着这场大雨能停止，在第 $1$ 天的雨结束时期待值为 $0$ ，之后在每天的雨结束时Soyo会把当天的雨势与前一天对比，如果当天的雨势相较前一天变小了，她的期待值就会上升，反之则会下降，上升或下降的数值等同于两天雨势差值的绝对值，即在第 $i$ $(1 < i \leq n)$ 天的大雨结束时Soyo的期待值变化的数值等于 $|a_i - a_{i-1}|$。

Tomori在大雨降临之前知道了这场大雨的信息，并被给予了交换两天雨势大小的能力，她想使用至多一次交换使得在第 $n$ 天的大雨结束时Soyo的期待值最大来迎接久违的晴天，请你输出这个最大值。

输入格式

一行一个正整数 $t$ $(1 \leq t \leq 10^4)$，表示有 $t$ 组数据。

每组数据的第一行有一个正整数 $n$ $(1 \leq n \leq 10^5)$，表示下雨的天数。

每组数据的第二行有 $n$ 个正整数，其中第 $i$ 个正整数 $a_i$ $(1 \leq a_i \leq 10^9)$ 表示第 $i$ 天的雨势大小。

保证所有数据中 $n$ 的总和不超过 $10^5$。

输出格式

对于每组数据输出一行

每行一个整数，表示Soyo期待值的最大值。

样例

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

5
3