سریال


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

میلاد و پارسا که از رسیدن به مرحله‌ی نهایی کدکاپ ۳ جا ماندند، از بیچارگی به دیدن سریال رو آوردند.

سریالی که تصمیم به تماشای آن گرفته‌اند nn قسمت دارد. آن‌ها برنامه‌ریزی کرده‌اند که قسمت ii-ام را در روز aia_i ببینند. برای اینکه دچار اعتیاد به سریال نشوند در یک روز بیشتر از یک قسمت نمی‌بینند و قسمت‌ها را به ترتیب خواهند دید. (یعنی: ai<ai+1a_i < a_{i+1})

میلاد و پارسا می‌خواهند علاوه بر لذتی که از دیدن سریال می‌برند زبانشان نیز قوی بشود. اگر طول بیشترین تعداد روز متوالی که در هر روزش یک قسمت سریال می‌بینند xx باشد، زبان آن‌ها به سطح xx می‌رسد.

برای بیشینه کردن میزان یادگیری زبان، آن‌ها می‌توانند حداکثر kk بار عملیات زیر را انجام دهند: عدد ii-ام (aia_i) را انتخاب کنند و آن را برابر با xx قرار دهند به صورتی که ai1<x<ai+1a_{i-1} < x < a_{i+1}. (ممکن است با عملیات‌های پیش از این عملیات هریک از ai1a_{i-1} و یا ai+1a_{i+1} تغییر کرده باشند و برابر مقدار اولیه‌شان نباشند؛ اینجا مقدار کنونی پس از انجام تغییرات پیشین مدنظر است.)

بیشترین سطح زبانی که آنها می‌توانند پس از دیدن سریال با انجام حداکثر kk عملیات داشته باشند چقدر است؟

ورودی🔗

در سطر اول ورودی دو عدد طبیعی nn و kk با فاصله از هم آمده است. سپس در سطر بعد nn عدد a1,a2,...,ana_1, a_2, ..., a_n آمده است.

1kn100 0001 \le k \le n \le 100\ 000 1a1<a2<...<an1<an1091 \le a_1 < a_2 < ... < a_{n-1} < a_n \le 10^9

خروجی🔗

در تنها سطر خروجی بیشترین سطح زبانی را که آنها می‌توانند پس از دیدن سریال با انجام حداکثر kk عملیات داشته باشند چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3 1
1 2 4
Plain text

خروجی نمونه ۱🔗

3
Plain text

ورودی نمونه ۲🔗

5 2
1 3 5 6 8
Plain text

خروجی نمونه ۲🔗

4
Plain text