3 Problem 3 (25 points total) Let A be some array of n numbers, with no duplicated elements, and re- call that Rank(x)- k if x 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 a is Now, let us define a number x in A to be special if x-InverseRank(x) the kth largest element of A 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: array A of length n Output: return a special number x in A, or return "no solution" if none exists. Questions: Part 1 (5 points): Give pseudocode for a O(nlog(n)) algorithm for the above problem . Part 2 (20 points): Give pseudocode for a O(n) recursive algorithm for the above problem. Give a brief justification for why the algorithm is correct. The recurrence formula for your algorithm should be T(n)