- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
برای دیدن یک بازی فوتبال $n$ نفر پشت دیوار استادیوم صف کشیده‌اند. ارتفاع قد نفر $i$ام در این صف $h_i$ است.
برای اینکه همه‌ی این افراد بتوانند نمای بهتری از زمین بازی داشته باشند، می‌خواهیم تعدادی جعبه زیر پای این افراد قرار دهیم تا ارتفاعی که روی آن قرار می‌گیرند بیشتر شود.
هر جعبه باعث می‌شود که ارتفاع قد یک نفر ۱ واحد افزایش پیدا کند.
زمانی می‌گوییم عدالت برقرار شده که ارتفاعی که هر دو نفر دارند بازی را تماشا می‌کنند حداکثر $d$ واحد اختلاف داشته باشد.
از شما می‌خواهیم برنامه‌ای بنویسید که کمترین تعداد جعبه را مشخص کند که با کمک آن می‌توانیم عدالت را برقرار کنیم.
ورودی
در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $d$ که با یک فاصله از هم جدا شده‌اند، آمده است.
$$1 \leq n \leq 500 , 000, \quad\quad 0 \leq d \leq 10^9$$
در $n$ سطر بعدی، اعداد صحیح $h_1, h_2, \dots, h_n,$ که با یک فاصله از هم جدا شده‌اند آمده است.
$$1 \leq h_i \leq 10^9$$
خروجی
در تنها سطر خروجی، کمترین تعداد جعبه لازم برای برقراری عدالت را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
3 1
1 2 8
خروجی نمونه ۱
11
ورودی نمونه ۲
4 0
1 5 3 6
خروجی نمونه ۲
9
ورودی نمونه ۳
1 3
5
خروجی نمونه ۳
0
ارسال پاسخ برای این سؤال