eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 3 seconds
Memory limit 512 MiB

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

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

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

Input data

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

Output data

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

Examples

Input example #1
3 0
3 2 3
Output example #1
1
Author Олег Петров
Source Летняя школа Севастополь 2013, Волна 2, День 6