When the number of elements ~N~ is small, it's possible to simulate the algorithm swap by swap. The complexity of this algorithm is ~\mathcal O(N^2)~, and it will surely work for ~N~ up to ~5000~, and the problem statement guarantees that in most of the test cases it will be at most ~100~.

For longer arrays, we need an algorithm more efficient than simulation. Suppose in some phase the number ~X~ is to be moved to its final position. The number of swaps in that phase is the difference between the current and final positions of ~X~. The final position is known, it is exactly ~X~, but the current position isn't.

The current position of ~X~ can be calculated from its starting position, provided sufficient information about numbers moved in previous phases. More precisely, each number moved in an odd phase (when numbers are moved to the left) that was initially to the right of ~X~ "jumped over" ~X~ during its phase and because of this ~X~ moved one place to the right. Similarly, each number moved in an even phase that was initially to the left of ~X~ will move ~X~ one place to the left.

These two numbers (how much ~X~ has moved left and right) can be efficiently calculated (in logarithmic complexity) using two Fenwick trees; one for odd phases and one for even phases. There is also a similar solution which uses only one Fenwick tree. Such a solution is implemented in the official source code.

Whenever a task includes smaller and larger constraints with algorithms of vastly different implementation complexity to solve them, it is a good idea to include both algorithms in the source code, and determine which one to use at runtime, depending on ~N~. That way, if there is an error in the more complex algorithm, we don't lose points on the smaller test cases.