Busy Beaver 喜欢在 MIT 的 Banana Lounge 度过他的下午。他决定通过堆叠香蕉箱来帮忙！他需要收集 $N$ 个连续房间里的库存，这些房间排成一行，从左到右编号为 $1$ 到 $N$。由于 MIT 建筑独特的结构，每个房间 $i$ 都有一个特定的天花板净空高度 $h_i$。

Busy Beaver 需要选择一个房间 $k$ ($1 \le k \le N$) 作为主枢纽（Main Hub）。然后，他的 $N$ 个朋友（每个房间一人）各自携带一叠垂直的香蕉箱，从他们的起始房间 $i$ 直接运送到枢纽房间 $k$。由于他们必须沿直线行走，他们能携带的香蕉箱最大数量受限于路径上的最小净空高度。

形式化地，从房间 $i$ 出发运送到枢纽房间 $k$ 的朋友所运送的香蕉箱数量为： 若 $i \le k$，则为 $\min(h_i, h_{i+1}, \dots, h_k)$。 若 $i > k$，则为 $\min(h_k, h_{k+1}, \dots, h_i)$。

在枢纽处收集的香蕉箱总数是所有 $N$ 个朋友运送的箱子数量之和，即： $$\sum_{i=1}^{k-1} \min(h_i, \dots, h_k) + h_k + \sum_{i=k+1}^{N} \min(h_k, \dots, h_i)$$

幸运的是，Busy Beaver 在 MIT 后勤部门有一位朋友。在朋友们开始搬运箱子之前，他可以请求翻新至多一个房间（不能是选定的枢纽房间 $k$），将其净空高度 $h_i$ 修改为任意值。

在选择最优枢纽位置 $k$ 并进行至多一次天花板翻新后，Busy Beaver 能在主枢纽收集到的香蕉箱总数最大是多少？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $N$ ($2 \le N \le 10^6$)。 每个测试用例的下一行包含 $N$ 个空格分隔的整数 $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$)。 所有测试用例的 $N$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即该测试用例的答案。

子任务

本题有两个子任务： (30 分)：所有测试用例的 $N$ 之和不超过 $3 \cdot 10^3$。 (70 分)：无附加限制。

样例

输入 1

2
5
1 10 1 10 1
5
10 10 10 10 10

输出 1

32
50

说明

在第一个样例中，最优选择是选择枢纽 $k = 2$ 并将 $h_3$ 翻新为至少 $10$，使得中间的三个朋友都能携带 $10$ 个箱子，总计 $32$ 个。 在第二个样例中，没有任何翻新可以增加香蕉箱的数量，因此答案为 $50$。