Masala F
O'sish zanjiri 2
Bir necha oy o'tgach, dars xonasidagi doskada faqat oxirgi kontest natijasi emas, haftalar bo'yicha o'sish ham ko'rina boshladi. Ustoz uchun bitta omadli kun yetarli emas edi: o'quvchi ketma-ket haftalarda avvalgidan kuchliroq ishlay olyaptimi, u aynan shuni kuzatardi.
\(n\) ta ketma-ket haftadagi natijalar \(a_1, a_2, \ldots, a_n\) berilgan. Siz biror uzluksiz kesma \(a_l, a_{l+1}, \ldots, a_r\) ni tanlaysiz. Kesmadagi har bir natijani o'z joyida qoldirish yoki istalgan kattaroq butun songa oshirish mumkin; kamaytirish mumkin emas.
Tuzatishdan keyin kesma qat'iy o'suvchi bo'lishi kerak: yangi qiymatlar \(b_l, b_{l+1}, \ldots, b_r\) bo'lsa, \(b_l < b_{l+1} < \cdots < b_r\) bo'lsin. Bitta natijadan iborat kesma har doim qat'iy o'suvchi hisoblanadi.
Barcha oshirishlar yig'indisi, ya'ni \((b_l - a_l) + (b_{l+1} - a_{l+1}) + \cdots + (b_r - a_r)\), \(k\) dan oshmasligi kerak.
Shu shartlarda mumkin bo'lgan eng uzun kesma uzunligi \(r - l + 1\) ni toping.
Birinchi qatorda ikkita butun son \(n\) va \(k\) beriladi \((1 \le n \le 2 \cdot 10^5,\ 0 \le k \le 10^{18})\).
Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) beriladi \((1 \le a_i \le 10^9)\).
Eng uzun mos kesma uzunligini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
5 3 3 1 2 1 2 |
3 |
| 2 |
4 0 1 2 2 3 |
2 |
| 3 |
4 10 5 1 1 1 |
3 |
Birinchi namunada \(2\)-haftadan \(4\)-haftagacha bo'lgan kesma \(1, 2, 1\). Oxirgi qiymatni \(3\) ga oshirsak, kesma \(1, 2, 3\) bo'ladi va jami \(2\) birlik oshirish sarflanadi. Bu \(k=3\) dan oshmaydi.
Ikkinchi namunada oshirishga umuman ruxsat yo'q \((k=0)\). Masalan, \(1, 2\) yoki \(2, 3\) kesmalari uzunligi \(2\) bo'lgan qat'iy o'suvchi kesmalardir; uzunligi \(3\) bo'lgan mos kesma esa yo'q.
Uchinchi namunada oxirgi uchta qiymatni \(1, 2, 3\) ko'rinishiga keltirish mumkin; buning uchun jami \(3\) birlik oshirish yetadi. To'rttala qiymatni qat'iy o'suvchi qilish uchun esa birinchi \(5\) dan keyingi uchta qiymat kamida \(6, 7, 8\) bo'lishi kerak. Bu \(18\) birlik oshirish talab qiladi va \(k=10\) dan katta.
Telegram kanalimizga obuna bo'ling