D. Running Miles
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть улица с $$$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]$$$.

Входные данные

В первой строке находится единственное целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное значение $$$b_{i_1} + b_{i_2} + b_{i_3} - (r - l)$$$ для некоторого отрезка $$$[l, r]$$$.

Пример
Входные данные
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
Выходные данные
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$$$.