eolymp
bolt
Try our new interface for solving problems
Problems

Excellence

Excellence

Time limit 1 second
Memory limit 128 MiB

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 data

The first line contains a single positive integer n (1n10^5, 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 s[i] (1s[i]10^6), the rating of student i.

Output data

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

Examples

Input example #1
4
1
2
3
5
Output example #1
5
Source 2015 ACM North America - Pacific Northwest, Division 1, Problem E