جایگشت ‎$a_1,a_2,\ldots,a_n$‎ از اعداد ‎$1,2,\ldots,n$‎ داده شده است. ما در هر مرحله می توانیم عملیات زیر را روی جایگشت انجام دهیم.

‎ در این عملیات یکی از اعداد جایگشت مثل ‎$x$‎ را انتخاب می کنیم. سپس بقیه‌ی اعداد جایگشت به چهار دسته تقسیم می‌شوند. آنهایی که قبل از ‎$x$‎ آمده‌اند و از ‎$x$‎ کوچکترند، آنهایی که بعد از ‎$x$‎ آمده‌اند و از ‎$x$‎ کوچکترند، آنهایی که قبل از ‎$x$‎ آمده‌اند و از ‎$x$‎ بزرگترند و آنهایی که از ‎$x$‎ بزرگترند و بعد از آن آمده‌اند. در انتهای این عملیات هر کدام از این چهار دسته نسبت به خودشان مرتب می‌شوند. مثلا اگر اعدادی که قبل از عدد ‎$x$‎ در جایگشت آمده‌اند و از ‎$x$‎ کوچکترند، ‎$a_{i_1},\ldots,a_{i_k}$‎ باشند که ‎$i_1\leq i_2\leq \ldots \leq i_k$‎ در پایان این عملیات این ‎$k$‎ عدد طوری در جایگاه‌های ‎$i_1,\ldots‎, ‎i_k$‎ قرار می‌گیرند که به ازای هر ‎$j < l$‎ عدد قرار گرفته در جایگاه ‎$i_j$‎ کمتر از عدد جایگاه ‎$i_l$‎ باشد.

‎ الگوریتمی از ‎$O(n)$‎ ارایه دهید که یک جایگشت از ورودی بگیرد و تعیین کند که آیا می‌توان با تعداد متناهی از این عملیات‌ها جایگشت را مرتب کرد یا نه. ‎

‎ نتیجه‌ی عملیات فوق روی عدد $5$ در جایگشت $‎3, 8, 1, 7, 5, 4, 6, 2‎$ جایگشت $‎1, 7, 3, 8, 5, 2, 6, 4‎$ خواهد بود. ‎

• سوال قبل