(This is a continuation of problem 6 on hw assignment 4, which was itself based on problem 8-5 on page 207 of CLRS 3rd edition.) Recall an array A[1 ... n] is k-sorted if and only if the (n k + 1) consecutive k-fold averages of A[1 ... n are sorted: EjEk-2A[j] +1 A[j] k for 1 sisn - k. Observe that if n = k, then any array of length n is k-sorted, since there is only one k-fold average in this case. We may also define any A[1 ...n] to be k-sorted if n