공지 확인 시간의 가운데

문제

한 회사는 사내 메신저로 새 업무 안내를 보낸 뒤 직원들이 공지를 확인하기까지 걸린 시간을 조사했다. 조사 대상 직원 수는 홀수이며, 모든 대상 직원은 공지를 확인했다. 각 직원의 확인 시간은 공지가 전송된 순간부터 처음 확인한 순간까지 걸린 분 단위의 음이 아닌 정수로 기록된다. 전송된 분에 바로 확인한 직원의 시간은 0이다. 관리자는 다음 공지를 보낼 때 참고할 대표 시간을 하나 정하려 한다. 일부 직원이 아주 늦게 확인한 경우에도 대표 시간이 지나치게 커지지 않도록, 기록된 시간들을 작은 순서대로 나열한 뒤 정확히 가운데에 놓인 시간을 사용하기로 했다. 직원 수가 N명이라면 작은 순서로 나열한 기록 중 (N+1)/2번째 기록의 값이 대표 시간이다. 순서는 1번째부터 센다. 같은 확인 시간이 여러 번 기록될 수 있다. 이때 같은 값을 하나로 합치거나 삭제하지 않고, 직원 한 명의 기록을 각각 한 칸씩 차지하도록 나열해야 한다. 예를 들어 확인 시간이 2, 2, 8이라면 작은 순서로 나열해도 2, 2, 8이며 가운데 값은 2다. 같은 시간에 확인한 직원들 사이의 순서는 대표 시간에 영향을 주지 않는다. 입력에 주어진 시간의 순서는 직원 명단의 순서이며, 시간의 크기순으로 주어진다는 보장은 없다. 직원의 이름이나 번호를 출력할 필요는 없고 대표 시간만 구하면 된다. 조사 대상이 한 명뿐이라면 그 직원의 확인 시간이 그대로 대표 시간이 된다. 모든 직원의 확인 시간이 같거나 모두 0인 경우도 가능하며, 이때도 같은 규칙을 적용한다. 주어진 확인 시간들을 이용하여 다음 공지 작성 화면에 표시할 대표 시간을 구하는 프로그램을 작성한다.

입력

첫째 줄에 조사 대상 직원 수 N이 주어진다. N은 1 이상 999 이하의 홀수인 정수다.
둘째 줄에 각 직원의 확인 시간 T1, T2, …, TN이 공백으로 구분되어 주어진다. 각 Ti는 0 이상 10,000 이하의 정수다.

출력

작은 순서로 나열했을 때 가운데에 놓이는 확인 시간을 정수 하나로 출력한다.

5
12 0 7 3 20

7

7
6 1 6 9 6 2 6

6

1
0

0

출처: Devin.KR 자체 제작