Counting inversions in an array of 1 to N
You can count inversions efficiently by adapting mergesort, but the most intuitive way is to just count all pairs:

$$\text{inv}(A) = \sum_{i=1}^{|A|}\sum_{j=i+1}^{|A|}[A_j&lt;A_i]$$

Where $[A_j &lt; A_i] = 1$ when $A_j &lt; A_i$ and $0$ otherwise.