+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر ---------- یکی از دانش‌پژوهان ورزشکار المپیاد کامپیوتر، بعد از زدن سرویس پرشی در بازی والیبال مصدوم شده و خانم دکتر برای مداوای او به باشگاه آمده‌است. خانم دکتر بعد از مداوای او متوجه صف بلندی از دانش‌پژوهان المپیاد کامپیوتر روبروی در سایت می‌شود، یک صف بسیار بلند که برای اعلام نتیجه‌ی آزمون عملی دوم تشکیل شده‌است. به دلایل نامعلوم (احتمالن قوی بودن تست‌کیس‌ها) مدت زیادی است که بچه‌ها منتظرند و نتیجه‌ای اعلام نشده‌است. برای همین بچه‌ها خودشان سعی دارند رتبه‌ای حدودی برای خود تخمین بزنند. روش آن‌ها به این صورت است که $k$ نفر اول صف بر اساس عملکردی که در آزمون داشته‌اند هر کدام تخمینی اولیه از رتبه‌ی خود می‌زنند و بقیه‌ی افراد صف با توجه به رتبه‌ی افراد جلوی خود، یک رتبه تخمینی برای خود در نظر می‌گیرند. آن‌ها به ترتیب (ابتدا فرد $k+1$-ام ، سپس $k+2$-ام و ...)‌ به این صورت رتبه‌ی خود را تخمین می‌زنند که رتبه‌ی $k$ نفر جلوی خود را می‌پرسند (یعنی فرد $i$-ام صف از افراد $i-k$-ام تا $i-1$-ام صف رتبه‌‌ی تخمینی‌شان را می‌پرسد) و با توجه به این که خیلی خوش‌بین هستند، کوچکترین رتبه‌ای را که هیچ‌ یک از $k$ نفر جلویی برای خود در نظر نگرفته را به عنوان رتبه‌ی خود در نظر می‌گیرند. تصویر زیر تخمین شش نفر اول را در صورتی که $k=4$ باشد نشان می‌دهد.  # ورودی در سطر اول ورودی به ترتیب دوعدد طبیعی $k$ و $n$ آمده است. سطر دوم دنباله‌ی $a_{1}, a_{2}, ..., a_{k}$ را نشان می‌دهد که در آن $a_{i}$ تخمین اولیه فرد $i$-ام صف است. ممکن است در بین $k$ نفر اول دو نفر رتبه‌ی یکسانی تخمین زده باشند. $$1 \leq k \leq 1\ 000\ 000$$ $$k < n \leq 10^{12}$$ $$0 \leq a_{1},a_{2},...,a_{k} \leq 10^9$$ # خروجی در تنها سطر خروجی تخمینی که فرد $n$‌-ام صف از رتبه‌ی خود دارد را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۰ | $ k \le 500$ , $n \le 5\ 000$| | ۲ | ۲۰ | $ k \le 500$ | | ۳ | ۴۰ | $ k , n \le 100\ 000$ | | ۴ | ۲۰ |$ k \le 100\ 000$| | ۵ | ۱۰ |بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 5 4 7 2 2 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 6 4 7 2 2 ``` ## خروجی نمونه ۲ ``` 3 ``` ## ورودی نمونه ۳ ``` 7 12 1 2 3 4 3 2 1 ``` ## خروجی نمونه ۳ ``` 4 ``` (۲۴امین دوره المپیاد کامپیوتر - آزمون دوم - ۱۳۹۳/۰۵/۳۰)