Suppose that, instead of sorting an array, we just require that the elements increase on average. ~~

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: Etk-1 A[j] 2tk , Ail k for 1 si sn - 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