晨跑里程

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一条街道上有 $n$ 个景点，第 $i$ 个景点位于距离街道起点 $i$ 英里处，美丽值为 $b_i$。

你要从位置 $l$ 开始晨跑，到位置 $r$ 结束，并会经过区间 $[l,r]$ 内的所有景点。选择经过的景点不少于三个的路线，取其中美丽值最大的三个景点。路线价值等于这三个美丽值之和减去跑步距离 $r-l$。

求路线价值的最大值。

输入格式

第一行包含整数 $t$（$1\le t\le10^5$），表示测试用例数。

每个测试用例第一行包含整数 $n$（$3\le n\le10^5$）。第二行包含 $n$ 个整数 $b_i$（$1\le b_i\le10^8$）。

所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对每个测试用例输出一行最大路线价值。

样例输入 1

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

样例输出 1

8
1
22
299999996

数据范围