ある「同じ値どうしの対応」を固定し、\(A_i\) に対応するものが \(B_{p_i}\) となるような置換 \(p\) を考えると、最小の swap 回数は転倒数 \(t=\mathrm{inv}(p)\) です。

自由に \(+2\) ずつ出来る（同じ場所を \(2\) 回連続で swap するなど）ことと置換の偶奇性から、コストの合計 \(c\) は以下を満たす必要があります。

• \(cK \ge t\) かつ \(cK \equiv t \pmod 2\)

各値について \(A\) の出現位置列と \(B\) の出現位置列を前から順に対応させたときの置換を \(P\) とします。 \(P\) は \(t\) が最小になる置換です。

また、\(P\) と偶奇が異なる置換のうち \(t\) が最小となる置換を \(Q\) とします。 このとき、\(P,Q\) それぞれについて最小の \(c\) を求めると、そのどちらか小さい方が答えとなります。

\(Q\) の求め方

同じ値どうしの対応を \(1\) ペア組み換えることにより、置換の偶奇を反転させることが出来ます。

あるペア \(l,r (l\lt r, A_l = A_r)\) について組み替えると、\(p_l, p_r\) が swap され、\(t\) が以下の値だけ増えます。

• \(2\cdot \#\{k\mid l<k<r,\ p_l<p_k<p_r\}+1\)

\(l \lt r, p_l \gt p_r\) を満たすペア \(l,r\) の組み替えを \(2\) ペア行うことで置換の偶奇を変えず \(t\) を減少させられることから、\(P\) からの組み換えは \(1\) 回までしか行わなくて良いことが示せます。

増加量の式を眺めると、\(x=i,y=p_i\) とした \(xy\) 平面上の点のうち、\((l,p_l)\) を左下 \((r,p_r)\) を右上とした矩形内の点の個数の最小値を求めれば良いことが分かります。
また、組み換えるペアとしては矩形が極小になるもの、つまり、同じ値の中で隣接する \(l,r\)（つまり、\(l \lt k \lt r\) かつ \(A_l = A_k = A_r\) を満たす \(k\) が存在しない）のみを考慮すれば十分であることが分かります。これは高々 \(N-1\) ペアしかありません。

アルゴリズムとしては、矩形を列挙してから平面走査 + BIT でまとめて数えることにより、\(O(N\log N)\) で求めることが出来ます。

注意点

\(K\) が奇数のときも \(P\) と偶奇が異なる置換を考慮に入れる必要があります。例：

3 99
1 1 2
2 1 1