Excellence

Interview

Time limit2sMemory limit256 MB

Summary

Pair all students into teams of two so the smallest team rating sum is as large as possible.

Level: Medium4 of 10
Topics: Greedy, Sorting, Two pointers
Solved: No attempts yet

Problem

The World Coding Federation is setting up a large online programming tournament for teams of two programmers. Judge David puts together the teams of the southeastern delegation. Every student joins exactly one team of two students, and the number of students who want to compete is even, so nobody is left out. David wants every team he sends to the tournament to reach some minimum total rating. The total rating of a team is the sum of the ratings of its two members.

Find the maximum value $X$ such that David can form the teams so that every team has a total rating of at least $X$ .

Input

The first line contains a positive integer $n$ , the number of students who want to enter the tournament ( $1 \le n \le 10^5$ , $n$ is even). Each of the next $n$ lines contains one integer $s_i$ , the rating of student $i$ ( $1 \le s_i \le 10^6$ ).

Output

Print on a single line the maximum value $X$ such that David can form teams where every team has a total rating of at least $X$ .

Examples3

Example 1
Input
```
4
1
2
3
5
```
Expected output
```
5
```
Example 2
Input
```
2
18
16
```
Expected output
```
34
```
Example 3
Input
```
4
13
12
19
14
```
Expected output
```
27
```