PKU 2388. Who's in the Middle

가운데 있는 것은 누구

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 7089	Accepted: 4265

설명

FJ는 그의 소떼중 가장 평균적인 소를 찾으려 한다. 그는 이 '중앙값' 젖소가 우유를 얼마나 생산하는지를 알고 싶어한다: 젖소들중 절반은 우유 생산량의 중앙값보다 크거나 같게 ; 절반은 우유 생산량의 중앙값보다 작거나 같게 우유를 생산한다.
홀수인 젖소의 개체수를 N (1 <= N < 10,000)이라 하고 젖소들의 우유 생산량을 정할 때(1..1,000,000), 최소한 절반 이상의 젖소는 중앙값보다 크거나 같게, 최소한 절반 이상의 젖소는 중앙값보다 작거나 같게 우유를 생산할 때, 주어진 우유 생산량의 중앙값을 구하시오.

입력
* 1번째 줄: 하나의 정수 N 

* 2번째 줄..N+1: 각 줄은 한 마리의 젖소가 생산하는 우유의 양인 하나의 정수를 포함한다.

출력

* 1번째 줄: 우유 생산량의 중앙값인 하나의 정수.

입력 예시

5
2
4
1
3
5

출력 예시

3

힌트

입력 세부사항: 

다섯마리 젖소의 우유 생산량은 1부터 5까지다.

출력 세부사항: 

1과 2는 3보다 밑에 있다.; 4와 5는 3보다 위에 있다.

출처

USACO 2004 November


역자주 : 오 제가 이런 것도 써보는군요. 힌트는 .. 예시로 주어진 입력과 출력에 한해서 인 듯 합니다. 실제 문제에서는 개체수의 범위와 우유 생산량의 범위가 전부 힌트보다 크니까요. 힌트를 사뿐히 무시해주는 센스를 발휘하셔도 좋으리라 생각됩니다.