最適な操作において、操作の回数は必ず0回か1回になります。

（2回以上操作を行うとき、それぞれの操作で選んだ区間の和集合における左端と右端を選んで一度操作を行えばよりよい解が得られます。）

初めから背の順に並んでいるとき（\(A_i=i\space\)のとき）は明らかに一度も操作をしないのが最適です。

以下、初め背の順で並んでいない場合について考えます。

このとき、\(A_1<A_2<\cdots<A_{x-1}>A_x\)を満たす\(x\)が存在します。

すると、

• \(1\leq l\leq x\leq r\leq N\)
• \(A_{l-1}<A_{r+1}<A_{r+2}<\cdots<A_N\)

（ただし、便宜的に\(A_0=0,A_{N+1}=N+1\)とします。）

ここで、\(1<l<x\)のとき\(A_1<A_l\)だから、\(l=1\)または\(l=x\)の場合のみ考えればよいです。

また、\(l\)を固定したとき、\(A_{l-1}<A_{r+1}\)かつ\(A_r<A_{r+1}<...<A_N\)をみたす\(r\)のうち最小の\(r\)を選ぶのが最適です。

したがって、以上の説明の通りに実装すれば\(O(N)\)で解くことができます。