(20) Let A[1n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

(2) List the five inversions of the array A = {2, 3, 8, 6, 1}

(3) What array with elements from the set {1, 2, , n} has the most inversions?

(10) Design an algorithm that determines the number of inversions in any permutation on n elements in (n log n) worst-case time.

(5) Suppose that the elements of A form a uniform random permutation of {1, 2, , n}, what is the expected number of inversions?