Задачі
Сучасне мистецтво
Сучасне мистецтво
Якщо вам довелось побувати на виставці сучасного мистецтва "Арсенал", то ви знаєте, яку величезну культурну цінність являють тамдешні експонати. Одеса вирішила не відставати від столиці, і силами жителів нашого містда було побудовано шедевр сучасного мистецтва - послідовність башт зі стаканчиків для кофе!
Експонат являє із себе \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
Виведіть єдине число - максимальну красоту експоната, яку можна отримати.
Вхідні дані #1
3 0 3 2 3
Вихідні дані #1
1