まず、操作を観察してみしょう。

\(P\) の先頭の要素を \(x\) として、これを \(Q\) に移動させることを考えます。すると、以下のような事実が見えてきます。

• 既に \(Q\) にある要素について
  • \(x\) より小さい要素が多数派ならば、\(x\) は \(Q\) の末尾に
  • そうでなければ、\(x\) は \(Q\) の先頭に
• 追加される（同数の場合はどちらでも構わない）。

この事実から、次のようなことも分かります。

• \(Q\) に \(x\) を追加する際、\(Q\) の長さを \(m\)、\(Q\) において \(x\) よりも小さい要素の数を \(k\) として、転倒数は \(\min(k, m - k)\) 増える。

以上の考察を基として、動的計画法でこの問題を解くことを考えます。

\(\mathrm{dp}_i :=\) \((\ N=i\) のときの答え \()\) とします。

\(\mathrm{dp}_{i-1}\) から \(\mathrm{dp}_{i}\) への遷移について考えます。

唐突ですが、\(S_x\) を「\(i\) 以下の正整数から、\(x\) 以外の \(i-1\) 個を選んだ集合」とします。

\(S_x\) の要素を並べ替えた順列 \(P_x\) としてあり得るもの全てに対する \(Q\) の転倒数の総和が \(\mathrm{dp}_{i-1}\) に一致することはすぐに分かります。

\(P_x\) の末尾に \(x\) を追加することを考えます。すると、\(P_x\) がどのように並んでいるかに拠らず、\(Q\) の転倒数は \(\min(x-1,i-x)\) 増加します。

よって、\(P_x\) を \((i-1)!\) 通りすべて考えて、\(S_x\) を固定したとき、これは \(\mathrm{dp}_i\) の値に \(\mathrm{dp}_{i-1} + (i-1)! + \min(x-1,i-x)\) だけ寄与することが分かりました。

これをすべての \(x\) について足し合わせることで、以下のような遷移式が導かれます。

\[ \mathrm{dp}_i = \mathrm{dp}_{i-1} \times i + (i-1)! \times \sum_{x=1}^{i} \min(x-1,i-x) \]

\(\sum_{x=1}^{i} \min(x-1,i-x)\) の値は、\(i\) の偶奇で場合分けを行うことで、等差数列の和の要領で簡単に求められます。

以上より、この問題を時間計算量 \(\Theta(N)\) で解くことが出来ました。

実装例 (Python)

DP を使わない解法も存在するようですが、Writer が理解できていないので、ユーザー解説を書いて頂けるととてもありがたいです。