题目描述

有 $n$ 块蛋糕排成一行，第 $i$ 块的重量为 $a_i$。定义这排蛋糕的美味度为相邻两块蛋糕重量之和的最大值：

你最多可以进行一次操作：选择一个连续子段 $a_l,a_{l+1},\ldots,a_r$（$1\le l\le r\le n$）并将它翻转（也可以选择不操作）。例如 $[5,2,1,4,7,3]$ 翻转子段 $[2,5]$ 后变成 $[5,7,4,1,2,3]$。

请求出操作后能达到的最大美味度。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

接下来依次给出 $T$ 组数据，每组两行：

• 第一行一个整数 $n$（$2\le n\le 2\times 10^5$），表示蛋糕块数；
• 第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^{18}$）。

同一个测试点内保证 $\sum n\le 5\times 10^5$，且 $T\le 2\times 10^4$。更精确的限制见子任务表。

输出格式

对每组数据输出一行一个整数，表示最大美味度。

3
6
5 2 1 4 7 3
3
32 78 78
3
69 54 91

12
156
160

2
8
999021 999021 999021 999021 999652 999021 999021 999021
2
1000000000000000000 1000000000000000000

1998673
2000000000000000000

样例解释

样例 1 第 1 组：$[5,2,1,4,7,3]$ 翻转 $[2,5]$ 得 $[5,7,4,1,2,3]$，美味度为 $\max(12,11,5,3,5)=12$；可以验证无法取得更大的美味度。

样例 1 第 2 组：$[32,78,78]$ 中 $78+78=156$ 已经是最优，不做操作。

样例 1 第 3 组：$[69,54,91]$ 翻转 $[2,3]$ 得 $[69,91,54]$，美味度为 $\max(160,145)=160$。

样例 2 第 1 组：不做操作时，与 $999652$ 相邻的两块都是 $999021$，美味度为 $999652+999021=1998673$；可以验证无法取得更大的美味度。

样例 2 第 2 组：只有两块，答案就是 $10^{18}+10^{18}=2\times 10^{18}$。

数据范围

下发文件

对于 $100\%$ 的数据：$1\le T\le 2\times 10^4$，$2\le n\le 2\times 10^5$，$\sum n\le 5\times 10^5$，$1\le a_i\le 10^{18}$。

下发文件见 sample.zip，其中 sample1、sample2 为上述两组样例，sample{i}_1 对应子任务 $i$ 的一个样例。

本题共 $5$ 个子任务，合计 $100$ 分，共 $20$ 个测试点，每点 $5$ 分，没有子任务依赖（各子任务独立计分）。

时间限制 $1$ 秒，空间限制 $256$ MiB。