定义长度为 $n$ 的数组 $a$ 的函数 $f(a)$：

$$f(a) = \text{cost} \;+\; \big(a_1 - a_2 + a_3 - a_4 + \cdots \pm a_n\big) $$

其中初始时 $\text{cost}=0$。

现有 Alice 和 Bob 得到一个长度为 $n$ 的数组 $a$，二人进行博弈：

• 轮流操作，Alice 先手；
• 总回合上限至多 $10^{100}$ 轮；
• 每一轮玩家必须选择以下任意一种操作：
  1. 直接终止整场游戏；
  2. 选取下标 $l,r$ 满足 $1\le l\le r\le n$，交换 $a_l$ 与 $a_r$； 本次操作会给 $\text{cost}$ 累加 $(r-l)$。

博弈目标：

• Alice 想最大化最终的 $f(a)$；
• Bob 想最小化最终的 $f(a)$； 两人均采取最优策略。

你的任务：求出游戏结束后 $f(a)$ 的最终值。

---

输入格式

多组测试用例。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试组数。

每组测试用例： 第一行一个整数 $n$（$1\le n\le 2\cdot 10^5$），数组长度。 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$）。

保证所有测试用例的 $n$ 总和不超过 $2\cdot 10^5$。

输出格式

对每组测试用例，输出双方最优策略下 $f(a)$ 的最终值。

---

样例输入

5
2
1000 1
5
9 9 9 9 9
4
7 1 8 4
6
1 14 1 14 1 15
9
31 12 14 22 89 6 78 25 91

样例输出

999
13
12
-7
265

---

样例说明

1. 第一组：Alice 最优策略是第一回合直接结束游戏。 此时 $\text{cost}=0$， $f(a) = 0 + 1000 - 1 = 999$。

2. 第四组：Alice 先交换 $a_1$ 与 $a_6$，之后 Bob 选择直接结束游戏。 此时 $\text{cost}=5$， $f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1 = -7$。