31233번 - 관광 상품

문제

민겸이는 새로운 관광 상품을 기획하려고 한다. 민겸이가 기획하려고 하는 관광 상품은 여러 명소를 관광하는 코스이다. 민겸이가 관광 상품에 넣을 수 있는 명소는 1ドル$번 명소부터 $N$번 명소까지 총 $N$개가 있으며, 각 명소는 양의 정수로 표현 가능한 아름다움을 가지고 있다. 민겸이는 관광 상품에 명소를 넣을 때, 연속된 번호의 명소만을 넣을 수 있다. 예를 들어, 민겸이는 3ドル$번, 4ドル$번, 5ドル$번 명소를 관광 상품에 넣을 수 있지만, 2ドル$번, 4ドル$번, 5ドル$번 명소를 관광 상품에 넣으면서 3ドル$번 명소를 제외할 수는 없다. 또한 민겸이는 관광 상품에 두 개 이상의 명소를 넣는다.

민겸이는 관광객이 관광 상품을 이용했을 때 얼마나 만족도를 얻는지 알아냈다. 관광객은 민겸이가 기획한 관광 상품의 명소들의 아름다움의 중앙값만큼의 만족도를 얻는다. 중앙값이란 어떤 $K$개의 수들에 대해 그 수들을 비내림차순으로 정렬했을 때 $\lfloor \frac{K+1}{2}\rfloor$번째 수를 말한다. 비내림차순이란, 각각의 수가 바로 앞에 있는 수보다 크거나 같은 경우를 말한다.

민겸이는 이 사실에 기반하여 관광객의 만족도를 최대화할 수 있는 관광 상품을 개발하였다. 민겸이가 개발한 관광 상품의 만족도가 얼마인지 알아보자.

입력

첫째 줄에 명소의 개수 $N$이 주어진다. $(2 \le N \le 200,000円)$

둘째 줄에 1ドル$번 명소부터 $N$번 명소까지 각 명소의 아름다움을 나타내는 1ドル$ 이상 10ドル^9$ 이하의 정수 $N$개가 공백으로 구분되어 주어진다.

출력

첫째 줄에 민겸이가 개발한 관광 상품의 만족도를 출력한다.

제한

힌트