CF1826D.Running Miles

There is a street with $n$ sights, with sight number $i$ being $i$ miles from the beginning of the street. Sight number $i$ has beauty $b_i$. You want to start your morning jog $l$ miles and end it $r$ miles from the beginning of the street. By the time you run, you will see sights you run by (including sights at $l$ and $r$ miles from the start). You are interested in the $3$ most beautiful sights along your jog, but every mile you run, you get more and more tired.

So choose $l$ and $r$, such that there are at least $3$ sights you run by, and the sum of beauties of the $3$ most beautiful sights minus the distance in miles you have to run is maximized. More formally, choose $l$ and $r$, such that $b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$ is maximum possible, where $i_1, i_2, i_3$ are the indices of the three maximum elements in range $[l, r]$.

街道上有 $n$ 个景点，其中第 $i$ 个景点距离街道起点 $i$ 英里。第 $i$ 个景点的美观度为 $b_i$。你希望从距离街道起点 $l$ 英里处开始晨跑，并在距离起点 $r$ 英里处结束。跑步过程中，你会经过（包括端点）所有位于区间 $[l, r]$ 内的景点。你特别关注此次跑步路线上美观度最高的 $3$ 个景点，但每跑一英里，你的疲劳程度都会递增。

因此，请选择 $l$ 和 $r$，使得你经过的景点数量至少为 $3$ 个，且“这 $3$ 个最美丽景点的美观度之和”减去“跑步总距离（英里）”的值最大化。更形式化地说，需选择 $l$ 和 $r$，使得 $b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$ 尽可能大，其中 $i_1, i_2, i_3$ 是区间 $[l, r]$ 内美观度最大的三个元素所对应的下标。

The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($3 \leq n \leq 10^5$).

The second line of each test case contains $n$ integers $b_i$ ($1 \leq b_i \leq 10^8$) — beauties of sights $i$ miles from the beginning of the street.

It's guaranteed that the sum of all $n$ does not exceed $10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$）—— 测试用例的数量。

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

每个测试用例的第二行包含 $n$ 个整数 $b_i$（$1 \leq b_i \leq 10^8$）—— 表示距离街道起点 $i$ 英里处景点的美观度。

保证所有 $n$ 的总和不超过 $10^5$。

For each test case output a single integer equal to the maximum value $b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$ for some running range $[l, r]$.

对于每个测试用例，输出一个整数，该整数等于在某个运行区间 $[l, r]$ 上表达式 $b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$ 的最大值。

In the first example, we can choose $l$ and $r$ to be $1$ and $5$. So we visit all the sights and the three sights with the maximum beauty are the sights with indices $1$, $3$, and $5$ with beauties $5$, $4$, and $3$, respectively. So the total value is $5 + 4 + 3 - (5 - 1) = 8$.

In the second example, the range $[l, r]$ can be $[1, 3]$ or $[2, 4]$, the total value is $1 + 1 + 1 - (3 - 1) = 1$.

在第一个例子中，我们可以选择 $l$ 和 $r$ 分别为 $1$ 和 $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$。