310390: CF1826D. Running Miles

D. Running Milestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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]$.

Input

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$.

Output

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]$.

ExampleInput

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

Output

8
1
22
299999996

Note

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$.

题目大意：
这是一道关于选择最美风景的题目。存在一条街道，街道上有n个风景点，风景点i距离街道起点的距离为i英里，风景点i的美观值为b_i。你希望在距离起点l英里的地方开始晨跑，在距离起点r英里的地方结束晨跑。在跑步过程中，你会看到跑步路线上的所有风景点（包括距离起点l英里和r英里的风景点）。你对跑步路线上的三个最美的风景点感兴趣，但随着跑步距离的增加，你会越来越累。

因此，你需要选择l和r，使得跑步路线上至少有3个风景点，且3个最美的风景点的美观值之和减去跑步距离（r - l）的值最大。更正式地说，需要选择l和r，使得b_{i_1} + b_{i_2} + b_{i_3} - (r - l)的值尽可能大，其中i_1, i_2, i_3是区间[l, r]内的三个最大元素的索引。

输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 10^5）——测试用例的数量。
每个测试用例的第一行包含一个整数n（3 ≤ n ≤ 10^5）。
每个测试用例的第二行包含n个整数b_i（1 ≤ b_i ≤ 10^8）——距离街道起点i英里的风景点的美观值。
保证所有n的总和不超过10^5。

输出数据格式：
对于每个测试用例，输出一个整数，表示某个跑步范围[l, r]的最大值b_{i_1} + b_{i_2} + b_{i_3} - (r - l)。题目大意： 这是一道关于选择最美风景的题目。存在一条街道，街道上有n个风景点，风景点i距离街道起点的距离为i英里，风景点i的美观值为b_i。你希望在距离起点l英里的地方开始晨跑，在距离起点r英里的地方结束晨跑。在跑步过程中，你会看到跑步路线上的所有风景点（包括距离起点l英里和r英里的风景点）。你对跑步路线上的三个最美的风景点感兴趣，但随着跑步距离的增加，你会越来越累。 因此，你需要选择l和r，使得跑步路线上至少有3个风景点，且3个最美的风景点的美观值之和减去跑步距离（r - l）的值最大。更正式地说，需要选择l和r，使得b_{i_1} + b_{i_2} + b_{i_3} - (r - l)的值尽可能大，其中i_1, i_2, i_3是区间[l, r]内的三个最大元素的索引。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 10^5）——测试用例的数量。 每个测试用例的第一行包含一个整数n（3 ≤ n ≤ 10^5）。 每个测试用例的第二行包含n个整数b_i（1 ≤ b_i ≤ 10^8）——距离街道起点i英里的风景点的美观值。 保证所有n的总和不超过10^5。 输出数据格式： 对于每个测试用例，输出一个整数，表示某个跑步范围[l, r]的最大值b_{i_1} + b_{i_2} + b_{i_3} - (r - l)。