e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

Горный туризм

Горный туризм

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

prb221

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

Задание

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

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

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

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

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

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
10 5
1 2 3 4 5 4 3 2 1 5
Выходные данные #1
18
Автор Даниил Нейтер
Источник 2009 XXII Всеукраинская олимпиада по информатике, Хмельницкий, Март 22 - 27, тур 1