시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 37 31 30 83.333%

문제

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.

입력

The first line of input contains a single positive integer n (1 ≤ n ≤ 105 , 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 (1 ≤ si ≤ 106), the rating of student i.

출력

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

예제 입력

4
1
2
3
5

예제 출력

5

예제 입력 2

2
18
16

예제 출력 2

34

예제 입력 3

4
13
12
19
14

예제 출력 3

27

힌트