+ محدودیت زمان: ۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به شما جایگشت $p_1,p_2,...,p_n$ از اعداد ۱ تا $n$ داده شده است. شما می‌توانید عملیات زیر را به هر تعداد دلخواهی(حتی صفر) روی جایگشت انجام دهید. + دو عدد $1\leq i < j \leq n$ انتخاب کنید که $\mid p_i-p_j \mid = 1 $ و $K \leq j - i$. بین تمام جایگشت‌هایی که از جایگشت اولیه می‌توان به آنها رسید کوچک‌ترین آنها از لحاظ لکسیکوگرافیکالی را پیدا کنید. # ورودی در خط اول ورودی دو عدد $n$ و $K$ به ترتیب داده شده‌اند. در خط دوم ورودی جایگشت $p_1,p_2,...,p_n$ داده شده است. $$1\leq n \leq 500\ 000$$ $$1\leq K \leq n - 1$$ # خروجی کوچکترین جایگشت از لحاظ لکسیکوگرافیکالی را در $n$ خط خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 2 4 2 3 1 ``` ## خروجی نمونه ۱ ``` 2 1 4 3 ``` ## ورودی نمونه ۲ ``` 5 1 5 4 3 2 1 ``` ## خروجی نمونه ۲ ``` 1 2 3 4 5 ``` ## ورودی نمونه ۳ ``` 8 3 4 5 7 8 3 1 2 6 ``` ## خروجی نمونه ۳ ``` 1 2 6 7 5 3 4 8 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- افراد ۱ تا $n$ تیم‌بندی شده‌اند و در یک صف قرار گرفته‌اند. به یک شیوه تیم بندی یک دنباله $a_1,a_2,...,a_n$ نسبت میدهیم به این شکل که به ترتیب عناصر دنباله را میسازیم: + در مرحله $i$ ام اگر فرد با شماره $i$ با فرد شماره $j$ هم‌تیمی بود به شکلی که $i>j$ $a_i$ را برابر $a_j$ قرار میدهیم. + در غیر این صورت $a_i$ را برابر مینیمم عدد طبیعی مانند $x$ قرار می‌دهیم که $x$ برابر هیچ کدام از اعداد $a_1,a_2,...,a_{i-1}$ نباشد. یک دنباله $a_1,a_2,...,a_n$ به شما داده شده است که تضمین می‌شود تیم‌بندی‌ای وجود داره که دنباله‌اش برابر آن شود. تعداد تیم‌بندی‌‌هایی را بشمارید که دنباله‌هایشان از لحاظ لکسیکوگرافیکالی کمتر یا برابر دنباله $a$ باشد. چون ممکن است این عدد خیلی بزرگ باشد، باقی‌مانده آن را به $1\ 000\ 007$ حساب کنید. # ورودی در خط اول ورودی یک عدد $n$ داده شده است. در خط دوم دنباله $a_1,a_2,...,a_n$ داده شده است. $$1 \leq n \leq 10\ 000$$ # خروجی باقی‌مانده تعداد تیم‌بندی‌های با شرایط گفته شده بر $1\ 000\ 007$ را در یک خط چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۳۰ | $$n \le 14$$| | ۲ | ۲۰ | $$n \le 100$$| | ۳ | ۲۰ | $$n \le 1\ 000$$| | ۴ | ۳۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 1 2 2 ``` ## خروجی نمونه ۱ ``` 4 ``` دنباله‌های معتبر: + $1 1 1$ + $1 1 2$ + $1 2 1$ + $1 2 2$ + $1 2 3$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دور دایره $n$ عدد چیده شده‌اند که مقدار $i$ امین عدد برابر $a_i$ است. دو نفر روی این دایره بازی میکنند به این شکل که در مرحله اول نفر اول یک خانه را انتخاب میکند و در مرحله دوم نفر دوم یک خانه بجز خانه نفر اول را انتخاب میکند. سپس در مراحل بعد با شروع از نفر اول، هرکس در نوبتش یک خانه که مجاور حداقل یکی از خانه‌های انتخاب شده‌اش است و تا به حال انتخاب نشده را انتخاب میکند. بازی زمانی تمام میشود که تمام خانه ها انتخاب شده باشند. نفر اول میخواهد جمع خانه‌هایی که در نهایت انتخاب کرده، بیشینه شود اما نفر دوم میخواهد این مقدار کمینه شود. اگر هر دو به بهترین شکل بازی کنند، جمع خانه‌هایی که نفر اول انتخاب میکند چند است؟ # ورودی در خط اول ورودی یک عدد $n$ داده شده است. در خط دوم دنباله $a_1,a_2,...,a_n$ داده شده است. $$2 \leq n \leq 500\ 000$$ $$1 \leq a_i \leq 2\ 000$$ # خروجی جمع خانه‌هایی که نفر اول انتخاب میکند را خروجی دهید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۰ | $$n \le 300$$| | ۲ | ۲۰ | $$n \le 5\ 000$$| | ۳ | ۲۰ | تضمین می‌شود که بهترین حرکت اول نفر اول این است که خانه یک را انتخاب کند.| | ۴ | ۴۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 7 6 8 4 ``` ## خروجی نمونه ۱ ``` 13 ``` ## ورودی نمونه ۱ ``` 5 1 1 1 1 1 ``` ## خروجی نمونه ۱ ``` 3 ```