An inversion of an array $A[1..n]$ is a pair of indices $(i,j)$ such that $1 \le i < j \le n$ and $A[i] > A[j]$.
The number of inversions shows how far the array is from being sorted: if it is already sorted then there are no
inversions while if it sorted in reverse order then the number of inversions is maximal.
