eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Современное икусство

Современное икусство

Лимит времени 3 секунды
Лимит использования памяти 512 MiB

Если вам довелось побывать на выставке современного искусства "Арсенале", то вы знаете, какую огромную культурную ценность представляют тамошние экспонаты. Одесса решила не отставать от столицы, и силами жителей нашего города был построен шедевр современного искусства - последовательность башенок из стаканов для кофе!

Экспонат представляет из себя n башенок различной высоты, расположенных последовательно от одного конца центральной улицы до другого. Однако, вандалы, не ценящие искусства и не имеющие чувства прекрасного, (а по совместительству - спортивные программисты), решив ночью выпить пару (или пару миллионов, делов то) чашек кофе, использовали m стаканов, тем самым уменьшив высоту некоторых башен. После данного злодеяния высота i-ой башни стала равна A_i. Нужно срочно достроить башни, при этом красота получившейся экспозиции должна быть как можно больше. Красотой всего этого шедевра называется максимальная длина красивой последовательности башен. Последовательность башен от l до r (1lrn) называется красивой, если H_l=H_{l+1}=...=H_r, где H_i - высота i-ой башни после добавления стаканчиков.

Данное задание было поручено самым ответственным девушкам Одессы, но они уехали в какую-то школу, так что пришлось послать его туда как задачу, а заодно и вы порешаете: выведите максимальную красоту башенок, которую можно получить, если добавить к существующим не более m стаканчиков. Учтите, что новых башенок создавать нельзя, равно как и убирать оставшиеся стаканчики.

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

В первой строке находятся два числа n (1n10^6) и m (0m10^9). В следующей строке через пробел перечислено n чисел A_{i }(1A_{i }≤ 10^9), i-ое число равно высоте i-ой башни.

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

Выведите единственное число - максимальную красоту экспоната, которую можно получить.

Пример

Входные данные #1
3 0
3 2 3
Выходные данные #1
1
Автор Олег Петров
Источник Летняя школа Севастополь 2013, Волна 2, День 6