Given is an array A of n integers. An ordered pair of A is a pair of integers (A [i], AD)) with i<=j. The maximum pair of A is an ordered pair, e.g., (Ai], AU)) with i

For examples, suppose A = (9,1,5, 4, 7} and then you should retum "(2, 5)" (i.e., the

maximum pair of A is (A [2], A [5])); suppose A = (-7,2, -1, -10, -6) and then you should

retum "(1, 2)" (i.e., the maximum pair of A is (A[1], A[21)); suppose A = (8,7,1, -4, -6) and

then vou should return any of "(1, 1)", "(2, 2)", "(3, 3)", "(4, 4)", and "(5, 5)" (i.e., the maximum pair of A is any of (8, 8), (7, 7), (1, 1), (4, 4), and (-6, -6))

Design a divide-and-conquer algorithm to solve the problem in 0 (nlog n) time. Your algorithm should use the divide-and-conquer technique. Please briefly present your idea first and then give the pseudocode. For your algorithm, please give the recurrence and the result.

No need to show how to solve the recurrence.