Məsələlər
Современное икусство
Современное икусство
Если вам довелось побывать на выставке современного искусства "Арсенале", то вы знаете, какую огромную культурную ценность представляют тамошние экспонаты. Одесса решила не отставать от столицы, и силами жителей нашего города был построен шедевр современного искусства - последовательность башенок из стаканов для кофе!
Экспонат представляет из себя \textbf{n} башенок различной высоты, расположенных последовательно от одного конца центральной улицы до другого. Однако, вандалы, не ценящие искусства и не имеющие чувства прекрасного, (а по совместительству - спортивные программисты), решив ночью выпить пару (или пару миллионов, делов то) чашек кофе, использовали \textbf{m} стаканов, тем самым уменьшив высоту некоторых башен. После данного злодеяния высота \textbf{i}-ой башни стала равна \textbf{A_i}. Нужно срочно достроить башни, при этом красота получившейся экспозиции должна быть как можно больше. Красотой всего этого шедевра называется максимальная длина красивой последовательности башен. Последовательность башен от \textbf{l} до \textbf{r} (\textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{n}) называется красивой, если \textbf{H_l=H_\{l+1\}=...=H_r}, где \textbf{H_i} - высота \textbf{i}-ой башни после добавления стаканчиков.
Данное задание было поручено самым ответственным девушкам Одессы, но они уехали в какую-то школу, так что пришлось послать его туда как задачу, а заодно и вы порешаете: выведите максимальную красоту башенок, которую можно получить, если добавить к существующим не более \textbf{m} стаканчиков. Учтите, что новых башенок создавать нельзя, равно как и убирать оставшиеся стаканчики.
\InputFile
В первой строке находятся два числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}) и \textbf{m} (\textbf{0} ≤ \textbf{m} ≤ \textbf{10^9}). В следующей строке через пробел перечислено \textbf{n} чисел \textbf{A}_\{i \}(\textbf{1} ≤ \textbf{A}_\{i \}≤ \textbf{10^9}), \textbf{i}-ое число равно высоте \textbf{i}-ой башни.
\OutputFile
Выведите единственное число - максимальную красоту экспоната, которую можно получить.
Giriş verilənləri #1
3 0 3 2 3
Çıxış verilənləri #1
1