* محدودیت زمان:‌ ۱ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ---------- اشکان برای سرگرم کردن پرهام یک بازی طراحی کرده‌است. او به پرهام یک جایگشت از اعداد صفر تا $n-1$ می‌دهد و از او می‌خواهد که با کمترین تعداد حرکت این جایگشت را مرتب کند. پرهام در هر نوبت می‌تواند جایگشت را به دو زیردنباله $S_1$ و $S_2$ افراز کند و جایگشت جدید را از کنار هم گذاشتن $S_1$ و $S_2$ به دست آورد. برای مثال او می‌تواند در یک نوبت جایگشت $<1, 3, 2, 0, 4, 5>$ را به دو زیردنباله $<3, 0, 4, 5>$ و $<1, 2>$ افراز کند و سپس به جایگشت $<3, 0, 4, 5, 1, 2>$ تبدیل کند. توجه کنید که اعضای زیردنباله به همان ترتیبی که در جایگشت هستند باید قرار گیرند، مثلا $<3, 4, 0>$ زیردنباله معتبری از جایگشت داده شده **نیست**. به پرهام کمک کنید که با کمترین تعداد حرکت جایگشت داده شده را مرتب کند. $$1 \le n \le 100\ 000$$ $$0 \le p_i \le n-1$$ # ورودی در خط اول ورودی عدد $ n $ آمده است. در خط بعد $n$ عدد $ p_0, p_1, ... , p_{n-1} $ آمده که اعداد جایگشت هستند. # خروجی در خط اول خروجی $k$، کمترین تعداد حرکت‌ مورد نیاز را چاپ کنید. در هر یک $ k + 1 $ خط بعدی $ n $ عدد چاپ کنید که خط اول خود جایگشت ورودی و پس از آن در هر خط جایگشتی که از روی جایگشت قبلی‌اش به دست می‌آید را چاپ کنید. اگر بیش از یک روش برای مرتب کردن جایگشت با کمترین تعداد حرکت وجود داشته‌باشد می‌توانید هر کدام را به دلخواه چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۱۱ | $n \le 7$ | |۲| ۲۳ | جایگشت نزولی است ($p_i > p_{i+1}$) و $n$ توانی از دو است یعنی $n=2^k$ | |۳|۴۶ | $n \le 100$| |۴|۲۰|بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 3 0 1 2 ``` ## خروجی نمونه ۱ ``` 0 0 1 2 ``` ## ورودی نمونه ۲ ``` 5 0 3 1 2 4 ``` ## خروجی نمونه ۲ ``` 1 0 3 1 2 4 0 1 2 3 4 ``` ## ورودی نمونه ۳ ``` 6 1 3 2 0 4 5 ``` ## خروجی نمونه ۳ ``` 2 1 3 2 0 4 5 3 0 4 5 1 2 0 1 2 3 4 5 ```

حل سؤال در بانک سؤالات