관광 상품

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

관광객은 관광 상품에 포함된 명소들의 아름다움의 중앙값만큼 만족도를 얻는다. $K$개의 수의 중앙값은, 그 수들을 비내림차순으로 정렬했을 때 $\lfloor \frac{K+1}{2}\rfloor$번째 수이다. 비내림차순은 각각의 수가 바로 앞의 수보다 크거나 같은 것을 뜻한다.

민겸이는 이 사실을 바탕으로 관광객의 만족도를 최대화하는 관광 상품을 개발하였다. 민겸이가 개발한 관광 상품의 만족도를 구하라.

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

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

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