ICPC Provincial

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

요약

3N개의 실력 값을 N개의 세 명짜리 팀으로 나눌 때, 모든 팀의 중앙값 중 최솟값을 최대화한다.

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

문제

The University of INC (UOI) is participating in an ICPC Provincial Contest, a qualifier contest for the ICPC Regional Contest. UOI has $3N$ students (numbered from $1$ to $3N$ ) who are eager to participate in the contest. There will be $N$ teams, each consisting of exactly $3$ students. Each student can only be assigned to only one team.

As the coach of UOI, you know that student $i$ has a skill rating of $A\_i$ . You define the strength of a team as the median of the skill ratings of its members.

In order to increase the chance for all UOI teams to qualify for the ICPC Regional Contest, you want to arrange the teams so that the strength of the weakest team is maximized. Determine the maximum strength of the weakest team.

입력

The first line consists of an integer $N$ ( $1 ≤ N ≤ 100\\, 000$ ).

The second line consists of $3N$ integers $A\_i$ ( $0 ≤ A\_i ≤ 4000$ ).

출력

Output a single integer representing the maximum strength of the weakest team.

예제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
```