各整数 \(k=1,2,\dots,N\) に対し、 \(A_i=k\) が成り立つ \(2\) つの \(i\) のうち、小さいほうを \(L_k\) 、大きいほうを \(R_k\) とします。

[1] 良い数列にするのに必要な操作回数

まず \(A\) を 良い数列 にするのに必要な操作回数について考えます。

これは最終的な 良い数列 を決め打つと転倒数と同じように計算することができますが、とくに \(2\) 種類の整数の位置関係により操作回数への寄与を考えると、以下の \(3\) パターンに分類できます。

• \((\dots,1,\dots,1,\dots,2,\dots,2,\dots) \rightarrow (\dots,1,1,\dots,2,2,\dots) \) or \((\dots,2,2,\dots,1,1,\dots) \)

• \((\dots,1,\dots,2,\dots,1,\dots,2,\dots) \rightarrow (\dots,1,1,\dots,2,2,\dots) \) or \((\dots,2,2,\dots,1,1,\dots) \)

• \((\dots,1,\dots,2,\dots,2,\dots,1,\dots) \rightarrow (\dots,1,1,\dots,2,2,\dots) \) or \((\dots,2,2,\dots,1,1,\dots) \)

それぞれについて寄与を計算すると、基本的には \(L_i\) が小さい \(i\) を左側にしたほうがいいことがわかります。よって \(A\) について \(L_i\) の昇順に並び替えることで 良い数列 にするのに必要な最小の操作回数を達成できます。

[2] 辞書式順序の最小化

[1]の考察を踏まえて辞書式順序の最小化を考えます。\(A\) における位置関係について \(1,2\) 番目のパターンについては並べ方は一意に決まりますが、 \(3\) 番目のパターンについてはどちらでもいいです。そうすると一連の操作後の良い数列 を \(1\) 項目から順に決めていく際、まだ登場していない整数 \(k\) のうち次の項に配置できるのは、\(L_{k'} < L_k\) を満たす \(k'\) すべてに対して \(R_{k} < R_{k'}\) が成り立つ \(k\) となります。

これをもとに答えを求める手順を整理します。\(1\) から \(N\) までの整数からなる順列 \(P\) を \(L_{P_i} < L_{P_{i+1}}\) が成り立つ順列とします。一連の操作後の良い数列 を \(1\) 項目から順に決めていく際、以下のようにすれば辞書式順序最小の 良い数列 \(ans\) が求まります。

• 整数列 \(X\) を \(X=(P_1,P_2,\dots,P_N)\) で初期化する。また、数列 \(ans\) を \(ans=()\) で初期化する。
• 以下の操作を \(N\) 回繰り返す
  • \(\displaystyle \min_{1 \leq i \leq k} R_{X_i} = R_{X_k}\) を満たす \(k\) に対する \(X_k\) のうち、もっとも小さい値 \(x\) を \(ans\) に \(2\) 回追加する。その後、\(x\) を \(X\) から取り除く

これを愚直に実装すると最悪 \(\Theta (N^2)\) かかります。

\(\displaystyle \min_{1 \leq i \leq k} R_{X_i} = R_{X_k}\) が成り立つ \(X_k\) を「低い項」と呼ぶことにすると、一度「低い項」になった \(X_k\) は以降常に「低い項」です。よって \(X\) から項が取り除かれた際にあらたに生じた「低い項」を高速に検出することができれば、「低い項」を優先度付きキューで管理することで上記の手順を高速に行うことができます。

[3] 「低い項」を検出するセグメント木

上記で述べたような項の削除と「低い項」の検出は

• 値1:区間内の \(R_{X_k}\) の最小値
• 値2:数列を区間内に限定した場合「低い項」になる項であって、数列全体では「低い項」になっていない \(X_k\) に対する \(R_{X_k}\) の最小値（存在しない場合 \(\infty\)）

を管理するセグメント木によって高速にできます。

（注：値2について「数列全体で『低い項』になっていない」と表記していますが、正確には「数列全体で検出済みの『低い項』になっていない」です）

まず項の削除については \(R_{X_k}\) を \(\infty\) に更新することで代用できます（つまり、\(k\) に対応する葉ノードの値1を \(\infty\) に更新する）。そしてあらたな「低い項」の検出については、数列全体を管理するノードがもつ値2が \(\infty\) でなければ、削除によって新たな「低い項」が生じたとわかります。値2では数列全体で「低い項」になっている \(X_k\) を除いて考えているため、あらたな「低い項」を検出した際にもセグメント木を更新する必要がありますが、これは \(k\) に対応する葉ノードの値2を \(\infty\) に更新すると考えればいいです。

実装についての詳細はこちらなど参照してください

項の削除や「低い項」に伴うセグメント木の更新は \(O(N)\) 回であるため、全体で \(O(N\log N)\) で答えを求めることができます。