thank you very much

Problem 1. ( 30 points) Comparison Sorts Suppose we modify the input of the comparison sort problem such that we assume that some elements of the input array are "nearly" at their correct position, as it is defined in the following. Input: A sequence A:=(a1,,an) of positive integers such that each element ai of A where i is divisible by 7 is in the sorted list of A either (i) at the correct position or (ii) one position away from its correct position. For example, given a sequence A:=(a1,,a55) the element a49 is in the sorted list of A in position 48,49, or 50. Show that the (nlogn) lower bound for the general comparison sort problem still holds for the above described constrained input of this