Hello everyone,
problems about swapping adjacent elements are quite frequent in CP, but they can be tedious.

Counting inversions

Let's start from a simple problem.

You are given a permutation of length $$$n$$$. In one move, you can swap two elements in adjacent positions. What's the minimum number of moves required to sort the array?

Claim

The result $$$k$$$ is equal to the number of inversions, i. e. the pairs $$$(i, j)$$$ ($$$1 \leq i < j \leq n$$$) such that $$$a_i > a_j$$$.

Proof 1

Let $$$f(x)$$$ be the number of inversions after $$$x$$$ moves.
In one move, if you swap the values on positions $$$i, i + 1$$$, $$$f(x)$$$ either increases by $$$1$$$ or decreases by $$$1$$$. This is because the only pair $$$(a_i, a_j)$$$ whose relative order changed is $$$(a_i, a_{i+1})$$$. So you need at least $$$k$$$ moves to sort the array.
On the other hand, if the array is not sorted you can