Optimal Cow Pairing

Farmer John finds that his cows are each easier to milk when they have another cow nearby for moral support. He therefore wants to take his \(M\) cows (where \(M\) is an even integer and \(2 \le M \le 10^9\)) and partition them into \(\frac{M}{2}\) pairs. Each pair of cows will then be ushered off to a separate stall in the barn for milking, and the milking in all these stalls takes place simultaneously.

Each cow has a distinct milk output. When cows with milk outputs \(A\) and \(B\) are paired, it takes \(A+B\) units of time to milk them both. Since all pairs are milked in parallel, the total time to complete the milking process is determined by the pair that takes the longest time.

Your task is to help Farmer John determine the minimum possible amount of time the entire milking process will take, by pairing the cows optimally. The optimal strategy is to pair the cow with the smallest milk output with the cow with the largest milk output, the second smallest with the second largest, and so on, so as to minimize the maximum pair sum.

inputFormat

The input consists of two lines:

• The first line contains an even integer \(M\) representing the number of cows.
• The second line contains \(M\) space-separated integers, each representing the milk output of a cow. All milk outputs are distinct.

outputFormat

Output a single integer which is the minimum possible time required for the entire milking process when the cows are paired optimally.

sample

4
4 2 1 8

9