\(P\) 内に \(1, 2, \ldots, k\) と昇順に並んでいる部分があるとき、\(1, 2, \ldots, k\) の順に移動させることで全体を \(1\) つ右に動かすことができます。これを繰り返して \(k\) の直後に \(k + 1\) が現れるようにし、次は \(1, 2, \ldots k + 1\) を動かしていくことにすれば、\(P\) を昇順に並び替えることができます。

この方針の操作回数を簡単に見積もってみます。\(1, 2, \ldots, k\) の並びを \(1, 2, \ldots, k + 1\) に拡大するために必要な操作回数は、高々 \(k(N - 1 - k)\) 回です。\(\sum_{k = 1}^{N - 1}k(N - 1 - k) = \frac{N(N - 1)(N - 2)}{6}\) であり、\(N = 100\) のとき、\(161700\) なので、\(2 \times 10^5\) 回に収まります（正確には、昇順に並び替えたあと添字を合わせる必要がありますが、これに必要な操作回数は \(N^2\) 回程度なので問題ありません）。