有一条街道,有 $$$n$$$ 景点,景点编号 $$$i$$$ 距街道起点 $$$i$$$ 英里。景点编号 $$$i$$$ 有美丽 $$$b_i$$$。您想要从街道起点开始晨跑 $$$l$$$ 英里并结束 $$$r$$$ 英里。当您跑步时,您将看到您跑步经过的景点(包括距起点 $$$l$$$ 和 $$$r$$$ 英里处的景点)。您对慢跑沿途最美丽的景点感兴趣,但每跑一英里,您就会变得越来越累。
因此,选择 $$$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)$$$。
示例
输入 #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
注意
在第一个示例中,我们可以选择 $$$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$$$。