e-olymp
Problems

Mountaineering (RU)

Mountaineering (RU)

Клуб активного туризма на планете Олимпия решил предложить клиентам маршрут вдоль живописного хребта. Хребет достаточно длинный и его трудно пройти сразу, поэтому в клубе ищут самый привлекательный из маршрутов ограниченной длины. Согласно результатам социального исследования туристы любят проходить по местам, которые выше чем другие на как можно большем промежутке, благодаря более широкому обзору и эйфории от ощущения высоты.

prb221

Для упрощения задачи хребет разделили на однометровые отрезки и определили среднюю высоту над уровнем моря каждого из них. Численное значение привлекательности каждого такого отрезка хребта равно количеству последовательных отрезков слева и справа, начиная с непосредственных его соседей, которые имеют высоту строго меньшую чем он сам. Сам отрезок в эту сумму не входит. Привлекательность маршрута вычисляется как сумма привлекательностей однометровых отрезков хребта, которые в него входят. Длина маршрута должна быть не больше чем T метров. Направление маршрута значения не имеет, поскольку не меняет его привлекательности. Маршрут может начинаться с любого отрезка хребта. Маршрут не может содержать разрывов, то есть в маршрут можно включать только последовательные отрезки хребта.

Задание

Напишите программу, которая по информации о высоте над уровнем моря каждого однометрового отрезка горного хребта вычислит привлекательность наиболее привлекательного маршрута длины не больше чем T метров.

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

Первая строка содержит два целых числа: N - длина всего хребта в метрах и T (1 ≤ T ≤ N ≤ 100 000) - ограничение на длину маршруту. Вторая строка содержит N целых чисел от 1 до 106 - высоты последовательных однометровых отрезков.

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

Вывести одно целое число - численное значение привлекательности самого привлекательного маршрута вдоль горного хребта длины не более чем T.

Time limit 1 second
Memory limit 64 MiB
Input example #1
10 5
1 2 3 4 5 4 3 2 1 5
Output example #1
18
Author Daniil Neyter
Source 2009 XXII All-Ukrainian Informatics Olympiad, Khmelnytskiy, March 22 - 27, Round 1