Pilot Rating
면접 대비시간 제한1초메모리 제한1024 MB
짝수 명의 파일럿을 두 명씩 짝지어 모든 팀 합의 최솟값을 최대로 만드는 값을 구한다.
문제
The Resistance is assigning pilots to new two-person X-wing Starfighters. General Leia has assigned you the task of putting teams together for the Red Squadron. Every pilot must be placed on exactly one 2- person team, and there are an even number of pilots. However, you would like to maintain a high skill level for each team by making sure that each of the teams has some minimum total rating. We define the total rating of a team to be the sum of the ratings of both pilots on the team.
You must determine the maximum value, X, such that you 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 ≤ 105, n is even), the number of pilots who volunteered for Red Squadron. Each of the following n lines contains one single integer si (1 ≤ si ≤ 106), the rating of pilot i.
출력
Print, on a single line, the maximum value, X, such that you can form teams where every team has a total rating greater than or equal to X.