- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سهراب مُرد (چون دیر به سهراب کمک رسید و در این مدت سهراب ذلت رو به عزت ترجیج داد و در شامگاهی ...)
واندرلند پس از مرگ سهراب روی خوش به خود ندید. اما طبق معمول کوشان که تکالیف و ددلاین‌ها برایش اهمیت بیشتری داشت تصمیم گرفت از فضای واندرلند دور بشه و شروع به تنظیم برنامه‌ی هفته آیندش کنه.
در واندرلند همه چیز عجیبه! مثلا در واندرلند یک هفته $n$ روز داره و کوشان نیز $n$ تمرین برای تحویل داره که تمرین $i$ام می‌بایست تا پایان روز $a_i$ تحویل داده بشه و به دلیل حجم بالای تمارین، هر تمرین یک روز کامل را برای حل کردن به خودش اختصاص می‌ده.
حال به کوشان کمک کنید تا برنامه خود را جوری تعیین کنه که هر تمرین تا پایان زمان مورد نظر تموم بشه و در عین حال کمترین نابه‌جایی را در ترتیب کارها اعمال کنه.
 |
|---|
| سمت چپ اون چایی به دسته |
ورودی
خط اول شامل عدد طبیعی $n$ است. در خط بعدی $n$ عدد آمده است که $i$امین آن‌ها مهلت تحویل تمرین $i$ام است.$$1 \le n \le 10^5$$ $$1 \le a_i \le n$$
خروجی
اگر کوشان نتواند طوری تمارین رو انجام دهد که هر تمرین تا پایان روز تعیین شده به پایان برسد $-1$ و در غیر این صورت از بین تمامی جایگشت‌های ممکن نابه‌جایی آن جایگشتی از انجام تمارین را خروجی دهید که کمترین نابه‌جایی را دارد.
مثال
ورودی نمونه ۱
3
3 2 1
خروجی نمونه ۱
3
در این نمونه مجبوریم کارها را به ترتیب ددلاینشان انجام دهیم. پس باید کارها را به ترتیب ۱ ۲ ۳ انجام دهیم که تعداد نابه‌جایی‌هایش ۳ می‌باشد.
ارسال پاسخ برای این سؤال