题目描述

一条街上有 $n$ 个景点，第 $i$ 个景点距离起点 $i$ 英里，其美观度为 $b_i$。你打算进行一次晨跑，起点在距离起点 $l$ 英里的地方，终点在距离起点 $r$ 英里的地方。在跑步过程中，你会看到所有经过的景点（包括起点 $l$ 和终点 $r$ 处的景点）。你对这次晨跑中遇到的三个最美的景点很感兴趣，但每跑一英里，你就会感到越来越累。

你需要选择 $l$ 和 $r$，使得你的跑步路程中至少包含三个景点，并且三个最美景点的美观度之和减去跑步距离最大化。

用更形式化的语言来说，你需要选择 $l$ 和 $r$，使得 $b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$ 的值最大，其中 $i_1, i_2, i_3$ 是区间 $[l, r]$ 中美观度最大的三个景点的索引。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 20$)，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $n$ ($3 \le n \le 10^5$)。 第二行包含 $n$ 个整数 $b_i$ ($1 \le b_i \le 10^8$)，表示第 $i$ 个景点的美观度。

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

输出格式

对于每组测试数据，输出一个整数，表示可能的最大值。

4
5
5 1 4 2 3
4
1 1 1 1
6
9 8 7 6 5 4
7
100000000 1 100000000 1 100000000 1 100000000

8
1
22
299999996

数据规模与约定

在第一个样例中，我们可以选择 $l=1$ 和 $r=5$。这样我们就经过了所有的景点，其中美观度最大的三个景点分别是索引为 $1, 3, 5$ 的景点，它们的美观度分别为 $5, 4, 3$。所以总价值是 $5 + 4 + 3 - (5 - 1) = 8$。 在第二个样例中，区间 $[l, r]$ 可以是 $[1, 3]$ 或 $[2, 4]$，总价值是 $1+1+1-(3-1)=1$。