最適解のうち、\(A_1,A_2\) のみに操作をする方法があることが証明できます。

証明をします。操作列のうち、\(A_1,A_2\) 以外の要素に操作をするものを \(1\) 個持ってきます。まず \(A_1,A_2\) に対する操作を全て行います。この時点で \(A_1 \le A_2\) である必要があります。この後に各 \(i(i \ge 3)\) にする操作は以下のいずれかです。

• $A_1 > A_i$ のとき：$A_i$ を $A_1$ まで上げるか、何もしない。
• $A_1 \le A_i \le A_2$ のとき：何もしない。
• $A_i > A_2$ のとき：$A_i$ を $A_2$ まで下げるか、何もしない。

ここで、\(A_1\) まで上げた \(A_i\) のうち最小のものを \(X\)(存在しない場合は \(A_1\))、\(A_2\) まで下げた \(A_i\) のうち最大のものを \(Y\)(存在しない場合は \(A_2\))とします。

元の操作列に対して、\(A_1,A_2\) 以外にした操作を全て取り消し、\(A_1\) を \(X\) に、\(A_2\) を \(Y\) にします。このとき \(A_1 \le A_i \le A_2\) を満たす整数 \(i\) の個数は減らず、操作回数は増えないことが確認できます。

よって、操作は \(A_1,A_2\) のみに行えばよいことが確認できました。以下、数列 \(B\) を \((A_3,A_4,\dots,A_N)\) を昇順ソートしたものとします。

最終的に \(A_1 \le B_i \le A_2\) を満たす \(i\) は区間になります。なので、\(B\) の長さ \(M\) の区間を全探索し、\([A_1,A_2]\) がその区間を包含するために必要な操作回数の最小値を求めればよいです。よって、上記を行うことによりこの問題を \(\mathrm{O}(N\log N)\) で解くことが出来ます。