Problem 2-1. [25 points] Zipline of Death For his upcoming beyond-the-grave performance, Kevel Enievil wants to build an awesomely long zipline in the CS 1205 mountain range. We represent the heights of the mountains in this range as an array of n distinct integers, AO ... A(n-1]. Assume that these heights are all distinct, and that n is a power of 2. Kevel needs to decide on two mountains as the endpoints of the zipline. To avoid premature deceleration, he needs to ensure that the endpoint mountains are higher than any mountains in between. Precisely, in the array A, he must find a contiguous subarray A[i]... A[j] for integers i, j (0 2 allow Kevel to zipline if and only if their largest two elements are the two endpoints. For example, if the array is [4, 1, 2,5, 3, 7,6], Kevel can build a zipline from 4 to 5 (having length 4) or a zipline from 5 to 7 (having length 3). In this problem, you'll develop a divide-and-conquer algorithm to find Kevel a zipline of maximum possible length. (a) [10 points] Suppose you split array A into two halves, Ao = A[0 : n/2] and A1 = A[n/2 : n], and suppose that the longest zipline has one endpoint eo in Ao and one endpoint ei in A1. Let ei = min(eo, e1) be the smaller endpoint. Prove that e; = max(A). (b) [15 points] Describe an efficient divide-and-conquer algorithm to find Kevel the zi- pline of maximum possible length in a given input array A0 : n] of n distinct integers. (For any algorithm you describe in this class, you should argue that it is correct, and argue its running time.) For full points, your algorithm should have a worst-case running time of O(n log n)