Minimizing inversions in an array with a single swap
Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i &lt; j$. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: $(i,j)$ and, for $i &lt; k &lt; j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i &lt; a_j$ and $a_i &gt; a_j$.

If $a_i &lt; a_j$ then the pair $(i,j)$ becomes an inversion, and for every $i &lt; k &lt; j$, there are three possible cases:


$a_k &lt; a_i &lt; a_j$: number of inversions stays the same.
$a_i &lt; a_j &lt; a_k$: number of inversions stays the same.
$a_i &lt; a_k &lt; a_j$: number of inversions increases by 2.


This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair $a_i,a_{i+1}$.

In contrast, if $a_j &lt; a_i$ then the number of inversions decreases by one plus twice the number of indices $i &lt; k &lt; j$ such that $a_j &lt; a_k &lt; a_i$. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair $(i,j)$ such that $a_j &lt; a_i$ and the number of indices $i &lt; k &lt; j$ satisfying $a_j &lt; a_k &lt; a_i$ is maximal. You take it from here.