题目描述

给定一个包含 $n$ 个整数的数组 $a$。你可以选择该数组的任意一个真子区间 $a_l, a_{l + 1}, \ldots, a_r$，即可以选择任意满足 $1 \le l \le r \le n$ 且 $r - l + 1 < n$ 的两个整数 $l$ 和 $r$。我们定义一个给定子区间的美丽值为如下表达式的值：

请你求出所有真子区间中美丽值的最大值。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$4 \leq n \leq 10^5$）——数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_{i} \leq 10^9$）——给定数组的元素。

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

输出格式

对于每个测试用例，输出一个整数，表示真子区间的最大美丽值。

说明/提示

在第一个测试用例中，最优的区间是 $l = 7$，$r = 8$。该区间的美丽值为 $(6 - 1) + (5 - 1) = 9$。

在第二个测试用例中，最优的区间是 $l = 2$，$r = 4$。该区间的美丽值为 $(100 - 2) + (200 - 1) = 297$。

由 ChatGPT 4.1 翻译

样例

4
8
1 2 2 3 1 5 6 1
5
1 2 3 100 200
4
3 3 3 3
6
7 8 3 1 1 8

9
297
0
14