Sogang Muscle Man

Interview

Time limit1sMemory limit1024 MB

Summary

Pair up N machines into floor(N/2) pairs plus possibly one leftover so the largest pair sum is minimized, and report that smallest possible maximum.

Level: Medium6 of 10
Topics: Greedy, Sorting, Two pointers, Binary search
Solved: No attempts yet

Problem

After watching Ronnie Coleman videos, Hyangbin decided to become a bodybuilder and went to Sogang Health Club for a PT consultation. He chose Sogang Health Club because members can pick which exercise machines they use during a PT session. But Sogang Health Club is always crowded, so in one PT session he can choose at most two machines.

Hyangbin wants to use each of the $N$ machines in the gym exactly once, so he planned to pick machines he had not used before in every PT session. To save money, he decided to use two machines per PT session whenever possible. For example, if the gym has $10$ machines in total, $5$ PT sessions use all of them. With $9$ machines he still has $5$ PT sessions, but in the last session he uses only one machine.

Choosing the machines put Hyangbin in a bind. Each machine causes a different amount of muscle loss. Some machines give little stimulation, so muscle loss is small, while others give strong stimulation, so muscle loss is large. Hyangbin fears muscle loss more than death, so he wants the muscle loss of any single PT session to stay at or below $M$ . Find the minimum possible value of $M$ . When a PT session uses two machines, the muscle loss of that session is the sum of the muscle losses of the two machines.

Input

The first line gives the integer $N$ , the number of exercise machines in Sogang Health Club. ( $1 \leq N \leq 10\ 000$ )

The second line gives the integers $t_1, t_2, \cdots, t_N$ , the muscle loss of each machine. ( $0 \leq t_i \leq 10^{18}$ )

Output

Print the minimum value of $M$ .

Examples1

Example 1
Input
```
5
1 2 3 4 5
```
Expected output
```
5
```