Есть улица с \(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]\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное значение \(b_{i_1} + b_{i_2} + b_{i_3} - (r - l)\) для некоторого отрезка \([l, r]\).
Примечание
В первом примере мы можем выбрать \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
8
1
22
299999996
|