操作後の \(s\) を辞書順最小にするためには

• \(s_1\) を可能な限り小さくする
• その上で \(s_2\) を可能な限り小さくする
• その上で \(s_3\) を可能な限り小さくする
• \(\vdots\)
• その上で \(s_N\) を可能な限り小さくする

という貪欲法を考えればよいです。

すぬけ君の手順は以下のように言い換えられます。

1. \(l=0, r=N+1\) とする。
2. すぬけ君は \(l <p <q<r\) を満たす整数 \(p,q\) を選ぶ(あるいは手順を終了する)。
3. \(s_p\) と \(s_q\) を入れ替える。
4. \(l=p, r=q\) として \(2.\) へ

先程の貪欲法を以下のように適用すればよいです。適切に実装すれば時間計算量 \(O(N)\) で動作し、十分高速です。

• \(p=1\) としてスワップを行うことで\(s_1\) を小さくできるならする。\(q\) は \(s_1\) が最も小さくなるようなものであって最大のものを選ぶ。
• \(p=2\) としてスワップを行うことで\(s_2\) を小さくできるならする。\(q\) は \(s_2\) が最も小さくなるようなものであって最大のものを選ぶ。
• \(\vdots\)