e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more

Excellence

The World Coding Federation is setting up a huge online programming tournament of teams comprised of pairs of programmers. Judge David is in charge of putting teams together from the Southeastern delegation. Every student must be placed on exactly one team of two students. Luckily, he has an even number of students who want to compete, so that he can make sure that each student does compete. However, he'd like to maintain his pristine reputation amongst other judges by making sure that each of the teams he fields for the competition meet some minimum total rating. We define the total rating of a team to be the sum of the ratings of both individuals on the team.

Help David determine the maximum value X, such that he can form teams, each of which have a total rating greater than or equal to X.

Input

The first line contains a single positive integer n (1n105, n is even), the number of students who want to enter the online programming tournament. Each of the following n lines contains one single integer si (1si106), the rating of student i.

Output

Print the maximum value X such that David can form teams where every team has a total rating greater than or equal to X.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
1
2
3
5
Output example #1
5
Source 2015 ACM North America - Pacific Northwest, Division 1, Problem E