조종사 평점

면접 대비

시간 제한1초메모리 제한1024 MB

요약

n명의 조종사를 두 명씩 짝지어, 가장 약한 팀의 합계 점수가 최대가 되는 값을 구합니다.

난이도: 쉬움10점 중 3점
유형: 정렬, 그리디, 배열
정답자: 아직 제출이 없습니다

문제

저항군은 새로운 2인용 X-wing 전투기에 조종사를 배정하고 있다. 레이아 장군은 레드 스쿼드론의 팀을 구성하는 일을 당신에게 맡겼다. 모든 조종사는 정확히 한 개의 2인 팀에 속해야 하며, 조종사 수는 짝수이다. 각 팀은 최소 총 평점 이상이어야 한다. 팀의 총 평점은 두 조종사 평점의 합이다.

모든 팀의 총 평점이 X 이상이 되도록 팀을 나눌 수 있는 X의 최댓값을 구하라.

입력

첫 줄에 양의 정수 $n$ ( $1 \le n \le 10^5$ , $n$ 은 짝수)이 주어진다. 레드 스쿼드론에 지원한 조종사의 수이다. 이어지는 $n$ 개의 줄에는 조종사 $i$ 의 평점 $s_i$ ( $1 \le s_i \le 10^6$ )가 한 개씩 주어진다.

출력

X의 최댓값을 한 줄에 출력한다.

예제1

예제 1
입력
```
4
2
1
3
5
```
예상 출력
```
5
```