| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 85 | 74 | 54 | 93.103% |
The University of INC (UOI) is participating in an ICPC Provincial Contest, a qualifier contest for the ICPC Regional Contest. UOI has 3ドルN$ students (numbered from 1ドル$ to 3ドルN$) 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 3ドルN$ integers $A_i$ (0ドル ≤ A_i ≤ 4000$).
Output a single integer representing the maximum strength of the weakest team.
2 1500 1700 1800 2300 2500 2600
1800
Team 1ドル$ consists of students 1ドル,ドル 3ドル,ドル and 5ドル,ドル while team 2ドル$ consists of students 2ドル,ドル 4ドル,ドル and 6ドル$. The strength of team 1ドル$ and 2ドル$ are 1800ドル$ and 2300ドル,ドル respectively. Other arrangements exist, but none allow the weakest team to have a strength higher than 1800ドル$.
1 2800 2100 3000
2800
There is only one team with the strength of 2800ドル$.
3 4000 0 4000 0 4000 0 4000 0 4000
0