让我们为长度为 $$$n$$$ 的数组 $$$a$$$ 定义一个函数 $$$f(a)$$$ 为 $$f(a) = \textrm{cost} + (a_1 - a_2 + a_3 - a_4 \cdots a_n)$$,其中 $$$\textrm{cost}$$$ 最初为零。
现在考虑这样的场景:给 Alice 和 Bob 一个长度为 $$$n$$$ 的数组 $$$a$$$。他们轮流玩最多 $$$10^{100}$$$ 回合的游戏,Alice 先玩。
在每个回合中,他们必须执行任何 一 (仅一项)以下操作:
- 结束 Alice 和 Bob 的游戏。
- 选择两个索引 $$$l,r$$$ 和 $$$1 \le l \le r \le n$$$ 并交换 $$$a_l$$$ 和 $$$a_r$$$;这会将 $$$(r - l)$$$ 添加到 $$$\textrm{cost}$$$ 中。
假设 Alice 尝试最大化 $$$f(a)$$$ 而 Bob 尝试最小化它。
你的任务是假设两个玩家都发挥最佳状态,确定 $$$f(a)$$$ 的最终值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 数组 $$$a$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,输出一个整数 - $$$f(a)$$$ 的最终值(假设两个玩家都处于最佳状态)。
示例
输入复制
521000 159 9 9 9 947 1 8 461 14 1 14 1 15931 12 14 22 89 6 78 25 91
输出复制
999 13 12 -7 265
注意
对于第一个测试用例,爱丽丝最好在第一回合结束游戏。
因此 $$$\textrm{cost} = 0$$$ 和 $$$f(a) = 0 + 1000 - 1 = 999$$$ 的最终值。
对于第四个测试用例,Alice 最好交换 $$$a_1$$$ 和 $$$a_6$$$,然后 Bob 在第一回合结束游戏是最优的。
因此 $$$\textrm{cost} = 5$$$ 和 $$$f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1=-7$$$ 的最终值。