Given an array, A, of elements that come from a total order, an inversion in A is a pair of elements that are in the wrong order, that is, a pair (i, j) where i < j and A[i] > A[j]. Show that the in-place version of insertion-sort,, runs in O(n + I) time, where I is the number of inversions in the array A.