A lake tour must seat exactly n paddlers (n is even) into n / 2 kayaks, two paddlers per kayak. Each kayak's load is the sum of its two paddlers' integer weights. Pair the paddlers so that the heaviest kayak load is as small as possible, and report that smallest achievable maximum load.
Input format
Line 1: an even integer n.
Line 2: n space-separated integers, the paddler weights.
Output format
A single integer: the minimum possible value of the maximum kayak load over all ways to form n / 2 pairs.
Constraints
- 2 ≤ n ≤ 100000, and
nis even. - -1000000000 ≤ each weight ≤ 1000000000