To lexicographically minimize the \(s\) after the procedure, the following greedy algorithm should be applied.

• Make \(s_1\) as small as possible.
• Satisfying the above, make \(s_2\) as small as possible.
• Satisfying the above, make \(s_3\) as small as possible.
• \(\vdots\)
• Satisfying the above, make \(s_N\) as small as possible.

The procedure by Snuke can be rephrased into the following.

1. Let \(l=0, r=N+1\).
2. Snuke chooses integers \(p,q\) such that \(l <p <q<r\) (or terminate the procedure).
3. Swap \(s_p\) and \(s_q\).
4. Set \(l=p, r=q\) and go to \(2.\)

Here, we should apply the greedy algorithm above, as follows. A proper implementation runs in \(O(N)\) time, which is fast enough.

• If a swap with \(p=1\) makes \(s_1\) smaller, do it. Here, choose the largest \(q\) that makes \(s_1\) the smallest.
• If a swap with \(p=2\) makes \(s_2\) smaller, do it. Here, choose the largest \(q\) that makes \(s_2\) the smallest.
• \(\vdots\)