26506번 - Pilot Rating 다국어

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 ≤ 10⁵, n is even), the number of pilots who volunteered for Red Squadron. Each of the following n lines contains one single integer s_i (1 ≤ s_i ≤ 10⁶), 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.