明らかに、操作回数を最小とするためには、集合 \(S_i, S_{i+1}\) が等しいような操作は行うべきではありません。

\(1\) から \(N\) までの数の並び替え \(P\) を仮想し、はじめ \((1, 2, \ldots, N)\) であるとします。\(S_i\), \(S_{i+1}\) に対して操作を行うとき、\(P_i, P_{i+1}\) を入れ替えましょう。このとき、次の命題を証明できます。

• どの時点でも、各 $i$ について、$S_i$ は $min(P[i:N])$ から $max(P[1:i])$ までの全ての整数からなる。

これは、初期状態では明らかに真です。この命題がいま成立するなら、集合 \(S_i, S_{i+1}\) に対して操作を行っても成立することを示しましょう。

もし \(P_i>P_{i+1}\) であれば、明らかに \(max(P[1:i]) = max(P[1:(i+1)])\) かつ \(min(P[i:N]) = min(P[(i+1):N])\) です。しかし、そうなると \(S_i\) は \(S_{i+1}\) と同じであり、これらについて操作を行う意味はありません。よって、\(P_i<P_{i+1}\) です。

すると \(S_i\cup S_{i+1}\) は \([min(P[i:N]), max(P[1:(i+1)])]\) に等しく、容易に \(min(P[i:N]) = min(P[(i+2):N]\cup \{P[i]\})\) かつ \(max(P[1:(i+1)]) = max(P[1:(i-1)]\cup \{P_{i+1}\})\) であることがわかるため、入れ替え後も命題中の性質が全ての \(i\) について成立します。

操作の過程より、操作回数が \(P\) の転倒数に一致することが簡単に分かります。従って、次の問題を解けばよいことになります。

• $1$ から $N$ までの数の並べ替えであって、各 $i$ について $max(P[1:i]) = R_i$ かつ $min(P[i:N]) = L_i$ であるものは存在するか？存在するなら、そのような並べ替えにおける転倒数としてありうる最小値を求めよ。

明らかに、各 \(i\) について \(L_i \le L_{i+1}\) かつ \(R_i \le R_{i+1}\) でなければなりません。また、\(L_i \neq L_{i+1}\) なら \(P_i\) は \(L_i\) と等しい必要があり、さらに \(P_N\) は \(L_N\) と等しい必要があります。同様に \(P_1 = R_1\) であり、\(R_i \neq R_{i+1}\) なら \(P_{i+1} = R_{i+1}\) である必要があります。

このように、\(P\) の要素のうちいくつかを特定できます。ある要素を二か所以上に割り当てる必要が生じたら、求めたい並べ替え \(P\) は存在しません。

まだ割り当てられていない残りの数についてはどうでしょうか。それらは、残った位置に昇順に並べるのが最適であることが容易にわかります。前からの最大値と後ろからの最小値に「違反」しないように残りの数を残りの位置に割り当てる方法が存在するなら、昇順に並べても矛盾しません。さらに、昇順に並べることで転倒数が最小化されることが容易にわかります！一石二鳥です。

よって、一部の要素の位置を特定し、残りの要素を昇順に並べ、前からの最大値と後ろからの最小値と合致するか確認し、合致するならその並べ方における転倒数を出力することで、問題を解くことができます。合計計算量は \(O(N\log{N})\) です。

おまけ: 計算量を \(O(N)\) に減らしてみてください