The input is a sequence of real numbers X = (x1, x2, , xn) in a non-decreasing order where n is even. The problem is to find a partition of X into n 2 pairs that minimizes the maximum value in S = {s1, s2, , s n 2 } where each si S denotes the sum of two numbers in pair i. For example, let X = (1, 2, 2, 4, 6, 6) and consider two partitions P1 = ((1, 2),(2, 4),(6, 6)) and P2 = ((1, 6),(2, 6),(2, 4)). Then, the maximum value of S1 = {3, 6, 12} resulted from P1 is 12 and the maximum value of S2 = {7, 8, 6} resulted from P2 is 8. Describe an O(n) time algorithm to solve the problem.