https://emtubasa.hateblo.jp/entry/2018/12/18/000000

解法

$p_i = i$ となっている部分は、 $p_{i-1}$ もしくは $p_{i+1}$ とスワップをすることで、 $p_i$ は条件を満たすことができます。
このとき、実はスワップ先の $p_{i-1}$ もしくは $p_{i+1}$ も条件を必ず見たします。なぜなら、この数列は順列なので、 $p_i=i$ だった場合は、 $p_{i-1}$ もしくは $p_{i+1}$ が $i$ となり、中身の値が $p$ の添え字と異なるからです。
このことを利用すると、前から順番に見ていき、 $p_i = i$ が存在した部分は $p_{i+1}$ とスワップする、という操作を繰り返すだけでよいことがわかります。
ただし、 $p_N = N$ だった場合のみ注意が必要で、この場合は $p_{N-1}$ とスワップをすれば十分です(この操作により、前の方の最善手が変わることはありません)。