Please answer Question 2:

Here is code for question 1:

6. [Total 6 pts] Given a one-dimensional array A[1.n](n2), we consider the problem of finding number of pairs (i,j), such that: 1i3A[j]. Use the following array as an example, the respective solution for this problem should be 7 and the corresponding pairs are: (1,6),(2,6),(3,5),(3,6),(4,5),(4,6),(4,8) Question \#1 [4 pts]: Let us use Pairs (A,1,n) to represent the solution, apply the divide-andconquer technique to design an algorithm which solves the problem. Clearly write your algorithm in pseudo-code similar as those in your textbook and feel free to add additional return values if needed. Question \#2 [2 pts]: Let T(n) be the running time of Pairs (A,1,n) in question #1. Write the recurrence expressing T(n) in terms of T(k) for some k3A[j]){totalPair++<.>