Lower Bound For Average I
There are n! ways to rearrange a list of n elements.
Recall that a rearrangement is called a permutation.
If we reverse a rearranged list, every pair that used to be an inversion will no longer be an inversion.
By the same token, all non-inversions become inversions.