$(10$ points$)$ The input is a sequence of real numbers $x=(x_1,x_2,$cdots,$x_n)$ in a non$-$decreasing order where

$n$ is even. The problem is to find a partition of $x$ into $\frac{n}{2}$ pairs that minimizes the maximum value in $S=$

$\{s_1,s_2,$cdots,$s_{\frac{n}{2}}\}$ where each $s_i$inS denotes the sum of two numbers in pair $i.$

For example, let $x=(1,2,2,4,6,6)$ and consider two partitions $P_1=((1,2),(2,4),(6,6))$ and $P_2=$

$((1,6),(2,6),(2,4)).$ Then, the maximum value of $S_1=\{3,6,12\}$ resulted from $P_1$ is $12$ and the maximum

value of $S_2=\{7,8,6\}$ resulted from $P_2$ is $8.$

Describe an $O(n)$ time algorithm to solve the problem.