جایگشت $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$ خواهد بود.