An array A of n integers is called semi-sorted if it is increasing until some index and then decreasing afterwards. In other words, there is some index 1 p n such that: A[i] < A[i + 1] for 1 i < p, and A[i] > A[i + 1] for p i < n. Note that in this case, A[p] is the maximum element of A. Give an algorithm with running time O(logn) that nds the maximum element of A, assuming that A is semi-sorted. Prove the correctness of your algorithm as well as do the analysis of the running time. Hint: We can use a modied binary search. The idea is if we pick an index i and compare A[i] with A[i+1] we can determine if i is before the peak (i.e. if i p) or if i is after the peak: if A[i] < A[i+1] then we can conclude that the maximum appears in A[(i + 1),...,n] and if A[i] > A[i + 1] then the maximum is in A[1,...,i]. For correctness, if your algorithm uses a loop, formulate a loop invariant (LI) - what remains to be true throughout all iterations of your loop so that when the loop terminates, LI implies that the maximum element of A is found? If your algorithm is dened by recursion, use Induction to prove the correctness.