思路

• 轮回只会影响两端时的 $A_1$ 或 $A_n$：

  • 区间不含两端（$1<l$ 且 $r<n$）：$A_1,A_n$ 不变，$S$ 不变，候选为 $A_1-A_n$。
  • 前缀（$l=1$）：可把任意 $A_k$（$1\le k\le r$）旋到首位，因此可达最大 $A_{\max}-A_n$。
  • 后缀（$r=n$）：可把任意 $A_k$（$l\le k\le n$）旋到末位，因此可达 $A_1-A_{\min}$。
  • 整段（$l=1,r=n$）：整体循环后 $S(A')=A_{i}-A_{i-1}$（把相邻对视为环，$A_0=A_n$），因此可达 $\max_{2\le i\le n}(A_i-A_{i-1})$ 以及 $A_1-A_n$（当环相邻对取 $(A\_1,A_n)$）。

• 综上答案为下式四者最大：

题目内容

远古风语者在风之谷留下了一串符文，每个符文刻录着能量强度，记作 $A_1,A_2,...,A_n$ ;

他定义这串符文的 平滑度 为 $S(A)=\sum^{n-1}_{i=1}(A_i-A_{i+1})$

现风语者可对一段连续符文区间施展 轮回咒，即对区间 $[l,r]$ 进行一次或多次 循环右移：

• 每次循环右移一步将符文 $A_r$ ，移至位置 $l$ ，其余元素依次后移；

恰好施展一次轮回咒后，得到新的符文序列 $A'$ 。请问能获得的最大平滑度 $max$ $S(A')$ 是多少?

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ ，表示测试组数；

除此之外，保证所有测试数据的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行输出一个整数，表示恰好执行一次轮回咒后能达到的最大平滑度。

样例1

输入

2
3
1 2 3
4
1 4 2 3

输出

1
3

说明

第一个样例中，将全段 $[1,3]$ 右移一步得到 {$3,1,2$} ，平滑度 $(3-1)+(1-2)=1$ ；

第二个样例中，将区间 $[1,4]$ 右移三步得到 {$4,2,3,1$} ，平滑度 $(4-2)+(2-3)+(3-1)= 3$ 。