در یک مجتمع اداری جهت رفاه کارکنان، یک پارکینگ با ظرفیت $n$ خودرو ساخته شد. اما چند روز پس از افتتاح پارکینگ مشخص شد که بعد از تمام شدن ساعت کاری، کارمندان هنگام خروج از پارکینگ به خاطر کوچکی درب خروجی، دچار ترافیک سنگینی می‌شوند. برای این منظور هیات مدیره‌ی مجتمع در یکی از جلسات خود تصمیم گرفت برای کاهش ترافیک هنگام خروج از پارکینگ، ترتیب خودروها را طوری تغییر دهد که هر کارمندی که زودتر کارش در مجتمع تمام می‌شود، بتواند زودتر آن‌جا را ترک کند. در ضمن می‌دانیم که هیچ دو کارمندی کارشان هم‌زمان تام نمی‌شود. خودروها در پارکینگ در یک صف قرار دارند. می‌دانیم که هیچ دو کارمندی کارشان هم‌زمان تمام نمی‌شود. خودروها در پارکینگ در یک صف قرار دارند. می‌دانیم که هیچ دو کارمندی کارشان هم‌زمان تمام نمی‌شود. خودروها در پارکینگ در یک صف قرار دارند. خودرویی که به درب خروجی نزدیک‌تر باشد، زودتر می‌تواند به درب خروجی برسد. $n$‌ مکان به شماره‌های $1,2,…,n$ در این پارکینگ وجود دارد که نزدیک‌‌ترین خودرو به درب خروجی در مکان اول و به همین ترتیب دورترین آن‌ها از درب، در مکان $n$ام پارک شده است.

می‌توان این گونه فرض کرد که یک جایگشت مانند $\pi$ از اعداد ۱ تا $n$ داریم که فردی که صاحب خودرو درمکان $i$ است، $\pi_i$ امین نفری است که کارش در مجتمع تمام می‌شود. در واقع $\pi_i -1$ نفر زودتر از فرد $i$ از مجتمع خارج می‌شوند. حال می‌خواهیم خودروها را طوری مرتب کنیم که خودرو در مکان $i$، پس از مرتب‌سازی در مکان $\pi_i$ قرار گیرد.

برای حل این مشکل، هیات مدیره تصمیم گرفت که از یک شرکت پیمان‌کار برای جابه‌جایی خودروها استفاده کند. این شرکت برای جابه‌جایی خوروها از چند راننده استفاده می‌کند. فرض کنید تعداد راننده‌ها برابر با تعداد خودروها است. به هر راننده چند خودرو واگذار می‌شود ولی یک خودرو به حداکثر یک راننده واگذار می‌شود. تعداد خودروهای واگذار شده، می‌تواند متفاوت باشد. مثلا ممکن است فقط به یک راننده تمام خودروها واگذار شود و یا به یک راننده هیچ خودرویی داده نشود. راننده‌ها به طور موازی کار می‌کنند. هر راننده می‌تواند فقط خودروهایی را که به او واگذار شده، در همان مکان‌ها جابه‌جا کند. دقت کنید که یک مدت زمانی که طول می‌کشد تا یک راننده خودروهای واگذار شده به خودش را از هر ترتیبی به هر ترتیب دیگر برساند، برابر با تعداد خودروهایی که به او واگذار شده، بر حسب دقیقه است. از آن‌جایی که راننده‌ها موازی با هم کار می‌کنند، مدت زمانی که طول می‌کشد تا پیمان‌کار تمام خودروها را به ترتیب دل‌خواهی قرا دهد، برابر با بیش‌ترین تعداد خودرویی است که به یک راننده سپرده شده است.

اما پس از چند روز یکی از اعضا برای کم کردن زمان تلف‌شده، استفاده از یک راننده‌ی دیگر را برای کاهش زمان کل پیشنهاد داد. وظیفه‌ی این راننده این است که در هر مرحله دو خودرو را باهم جابه‌جا کند. این راننده قبل از شرکت پیمان‌کار کار خود را آغاز می‌کند. جابه‌جایی هر دو خودرو برای این راننده یک دقیقه طول می‌کشد.

یعنی ابتدا می‌توانیم $k$ بار عمل جابه‌جایی را برای خودروها انجام دهیم. بعد از آن جایگشت را به چند مجموعه افراز می‌کنیم. فرض کنید بزرگ‌ترین مجموعه $l$ عضو دارد. این مجموعه‌ها را می‌توانیم با صرف $l$ دقیقه مرتب کنیم. بنابراین در کل به اندازه‌ی $l+k$ دقیقه زمان طول می‌کشد تا ترتیب خودروها را تغییر دهیم.

برای مثال فرض کنید که جایگشت $\pi$ برابر $\bigl\langle 4,3,1,6,5,2 \bigr\rangle$ باشد. می‌توانیم ابتدا خودروهای اول و آخر را جابه‌جا کنیم تا به جایگشت $\bigl\langle 2,3,1,6,5,4 \bigr\rangle$ برسیم که یک دقیقه طول می‌کشد. سپس خودروهای اول و دوم و سوم را به یک راننده و خودروهای چهار و ششم را به یک راننده‌ی دیگر می‌دهیم و خودرو پنجم را به هیچ راننده‌ای نمی‌دهیم. واضح است که با مرتب کردن هر دسته به جایگشت $\bigl\langle 1,2,3,4,5,6 \bigr\rangle$ می‌رسیم. این عمل نیز ۳ دقیقه طول می‌کشد. در نتیجه در ۴ دقیقه می‌توانیم جایگشت را مرتب کنیم.

برنامه‌ای بنویسید که:

• یک جایگشت از اعداد ۱ تا $n$ را از ورودی بخواند.
• کم‌ترین زمان لازم برای مرتب‌سازی خودروها را محاسبه کند.
• مقدار محاسبه شده را در خروجی بنویسد.

• در سطر اول ورودی، عدد $n$ قرار دارد.($1\leq n \leq 10^6$)
• در سطر بعد، $n$ عدد با یک فاصله نسبت به هم می‌آیند که یک جایگشت از اعداد ۱ تا $n$‌ است.

در یک سطر کم‌ترین زمان لازم برای تغییر دادن جایگشت ورودی به جایگشت $1…n$ را با توجه به اعمال تعریف شده در مسئله، بر حسب دقیقه بنویسید.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۰۰ مگابایت

• سوال بعد
• سوال قبل