Design a linear time divide and conquer algorithm to compute the problem.

2. (20 pts) Consider the following problem A[1 to n] of distinct integers Input: array , and integerx Output: the rank of the integer closest to x in A Here the rank means the minimum rank, i.e., the rank of the smallest in A is 1, that of the 2n smallest is 2, etc. Consequently if the element closest to x is the kth smallest of A, the output is k. For example, if All to 4H 8, 1, 5, 20) and x-4, the output is 2 because the closest to 4 is 5, having rank 2. If xa, the output can be either 1 or 2. Design a linear time divide and conquer algorithm to compute the problem. Write all of: o your basic method in 3-10 lines, o complete pseudo code, o proof of the algorithm correctness, and o that of the running time O(n) with the running time recurrence. Make your answers succinct but include everything necessary to reason the above