CF1826D Running Miles

有一条街道上有 $n$ 个景点，第 $i$ 个景点距离街道起点 $i$ 英里。第 $i$ 个景点的美丽值为 $b_i$。你想从距离起点 $l$ 英里处开始晨跑，到距离起点 $r$ 英里处结束晨跑。在跑步过程中，你会经过所有在 $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]$ 内美丽值最大的三个景点的编号。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示某个跑步区间 $[l, r]$ 下 $b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$ 的最大值。

在第一个样例中，我们可以选择 $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$。 由 ChatGPT 4.1 翻译