محدودیت زمان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت
منبع: CEOI 2018

چند وقتی هست که زورو پول لازم هست. او به همین منظور سعی بر راضی کردن پدر خود دارد تا گونی پولی به او اهدا کند. پدرش که نگران درس زوروست با او قرار می‌گذارد که اگر او پیشرفت تحصیلی راضی کننده‌ای داشته باشد، به او یک گونی پول می‌دهد. منظور او از پیشرفت تحصیلی یک دنباله ای از آزمون‌های زورو است که اگر به ترتیب زمان مرتب شان کنیم، نمرات آن‌ها یک دنباله صعودی تشکیل دهند. مقدار راضی کنندگی یک پیشرفت تحصیلی برابر با تعداد آزمون‌های آن است.

زورو که بد جور به فکر پول است ، می‌خواهد اخلاق را زیر پا بگذارد و تقلب کند. او یک بازه ی متوالی از لیست آزمون‌هایش (که به ترتیب زمان برگذاری مرتب شده اند) را به همراه عدد صحیح $d$ با رعایت $-x \le d \le x$ انخاب می‌کند و به تمام نمرات بازه انتخاب شده $d$ واحد اضافه می‌کند. دقت کنید که $d$ می‌تواند منفی باشد (ممکن است زورو غرق رد گم کردن شود و هدف اولیه خود را فراموش کند).

حال او از شما خواسته که به دادش برسید. با گرفتن تعداد آزمون‌های زورو ( $n$ ) و لیست نمرات او ( $A$ ) و عدد $x$ ، مقدار راضی‌کننده‌ترین پیشرفت تحصیلی پس از تقلب را برایش چاپ کنید.

ورودی

در خط اول ورودی به ترتیب دو عدد $n$ و $x$ با فاصله از هم آمده است.

در خط دوم ورودی $n$ عدد با فاصله آمده‌اند که نشان دهنده لیست نمرات زورو اند. نمرات به ترتیب زمانی داده شده اند. $1 \le n \le 200\ 000$ $0 \le x , A_i \le 10^9$

خروجی

تنها یک عدد چاپ کنید که برابر با بیشینه مقدار راضی کنندگی یک پیشرفت تحصیلی است.

زیر مسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۵	$n,x \le 10$
۲	۱۰	$n,x \le 50$
۳	۱۳	$n \le 1000$
۴	۱۰	$x = 0$
۵	۲۰	$x \le 5$ $n \le 5 \times 10^4$
۶	۱۷	$x = 10^9$
۷	۲۵	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

8 10
7 3 5 12 2 7 3 4

خروجی نمونه ۱

زورو می‌تواند بازه ی $[2,3]$ و $d = -5$ را انتخاب کند. بدین شکل $[-2,0,2,3,4]$ یک پیشرفت تحصیلی بهینه است.

ارسال پاسخ برای این سؤال