Largest Pair

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka have a set of \(n\) integers, where \(n\) is even.

While the set is not empty, they repeatedly choose the minimum and maximum numbers from it, write down their sum on a piece of paper, and remove the numbers from the set. If there are multiple maximum or minimum numbers, they choose an arbitrary one.

Your task is to find the largest number written on the piece of paper after processing all numbers from the set.

Input

The first line gives a single integer \(n\) — the initial number of integers in the set.

The next line gives \(n\) integers \(a_i\) separated by spaces — the numbers in the set.

Output

Print a single integer — the largest number written on the piece of paper.

Constraints

\(2 \le n \le 1000\), \(n\) is even.

\(1 \le a_i \le 10^9\),

Samples

Input (stdin) сopy	Output (stdout) сopy
4 6 4 9 2	11

Input (stdin) сopy	Output (stdout) сopy
8 11 4 9 7 10 3 9 4	16

Notes

In the first example, in the first step they will choose 2 and 9 (sum 11), and in the second — 4 and 6 (sum 10). The larger sum is 11, so the answer is 11.

In the second example, in the first step they will choose 3 and 11 (sum 14), in the second — 4 and 10 (sum 14), in the third — 4 and 9 (sum 13), in the fourth — 7 and 9 (sum 16). So the answer is 16.