ICPC Provincial

면접 대비

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

요약

3N명의 실력 점수가 주어질 때 세 명씩 N개 팀으로 나누어, 중앙값이 가장 낮은 팀의 중앙값을 최대로 만드는 값을 구합니다.

난이도: 보통10점 중 4점
유형: 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

UOI 대학은 ICPC 지역 예선의 예선 대회인 ICPC Provincial Contest에 참가한다. UOI에는 1번부터 $3N$ 번까지 번호가 붙은 $3N$ 명의 학생이 있고, 모두 대회에 나가기를 원한다. $N$ 개의 팀을 만들며, 각 팀은 정확히 3명으로 구성된다. 각 학생은 한 팀에만 배정될 수 있다.

학생 $i$ 의 실력 점수는 $A_i$ 이다. 팀의 강도는 팀원 실력 점수의 중앙값으로 정의한다. UOI의 모든 팀이 ICPC 지역 대회에 진출할 가능성을 높이려고, 가장 약한 팀의 강도가 최대가 되도록 팀을 구성하려 한다. 가장 약한 팀의 강도의 최댓값을 구하라.

입력

첫째 줄에 정수 $N$ ( $1 \le N \le 100000$ )이 주어진다. 둘째 줄에는 $3N$ 개의 정수 $A_i$ ( $0 \le A_i \le 4000$ )가 주어진다.

출력

가장 약한 팀의 강도의 최댓값을 한 줄에 출력한다.

예제3

예제 1
입력
```
2
1500 1700 1800 2300 2500 2600
```
예상 출력
```
1800
```
예제 2
입력
```
1
2800 2100 3000
```
예상 출력
```
2800
```
예제 3
입력
```
3
4000 0 4000 0 4000 0 4000 0 4000
```
예상 출력
```
0
```