4 Problem 4 (30 points) Let A be some array of n integers (possibly negative), with no duplicated elements, and recall that Rank(t) = k if I is the kth smallest element of A. Now define InverseRank(x) = n + 1 - Rank(x). It is easy to see that if InverseRank(x) = k, then r is the kth largest element of A. Now, let us define a number r in A to be special if I = InverseRank(). For example, if A = -9,8,1,-1, 2, then 2 is special because 2 is the 2nd largest number in the array, so InverseRank(2) = 2. Consider the following problem: Input: unsorted array A of length n Output: return a special number r in A, or return "no solution" if none exists. Questions: Part 1 (5 points): Give pseudocode for a O(n log(n)) algorithm for the above