Fixing a certain “correspondence between equal values”, consider a permutation \(p\) such that the element corresponding to \(A_i\) is \(B_{p_i}\). The minimum number of swaps is the number of inversions \(t=\mathrm{inv}(p)\).

From the fact that we can freely add \(+2\) (by swapping the same position twice consecutively etc.) and the parity of permutations, the total cost \(c\) must satisfy:

• \(cK \ge t\) and \(cK \equiv t \pmod 2\)

Let \(P\) be the permutation obtained by matching the sequence of occurrence positions in \(A\) with the sequence of occurrence positions in \(B\) from left to right for each value. \(P\) is the permutation that minimizes \(t\).

Also, let \(Q\) be the permutation with different parity from \(P\) that minimizes \(t\). Then, if we compute the minimum \(c\) for each of \(P\) and \(Q\), the smaller of the two is the answer.

How to compute \(Q\)

By changing the correspondence between equal values for one pair, we can flip the parity of the permutation.

When rearranging for some pair \(l,r\) (\(l\lt r, A_l = A_r\)), \(p_l\) and \(p_r\) are swapped, and \(t\) increases by:

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

From the fact that rearranging two pairs satisfying \(l \lt r, p_l \gt p_r\) can reduce \(t\) without changing the parity of the permutation, it can be shown that rearranging from \(P\) needs to be done at most once.

Looking at the formula for the increase, we need to find the minimum number of points within a rectangle with \((l,p_l)\) as the bottom-left and \((r,p_r)\) as the top-right among points on the \(xy\) plane with \(x=i,y=p_i\).
Also, it suffices to consider only pairs where the rectangle is minimal, that is, adjacent \(l,r\) among the same value (i.e., there is no \(k\) satisfying \(l \lt k \lt r\) and \(A_l = A_k = A_r\)). There are at most \(N-1\) such pairs.

As an algorithm, we can enumerate rectangles and count them all together using plane sweep + BIT in \(O(N\log N)\).

Caution

Even when \(K\) is odd, we need to consider permutations with different parity from \(P\). Example:

3 99
1 1 2
2 1 1