21556번 - 우물 파기 서브태스크

폴리매스 왕국의 사람들은 우물을 이용해 지하수를 마십니다. 지하수의 근원은 물의 돌이라고 알려져 있으나, 물의 돌의 정확한 위치를 알고 있는 사람은 아무도 없습니다.

최근 들어 인구가 늘어나자 물이 부족해졌습니다. 사람들은 이를 해결하기 위해 두 개의 우물을 더 파려고 합니다. 우물을 팔 수 있는 곳은 $N$곳이 있으며, 이들 중에서 $i$번 위치와 $j$번 위치에 우물을 파면 $A_i+A_j$만큼의 이익을 얻을 수 있습니다.

우물을 파는 위치를 적당히 정해서 최대 이익을 얻는 것이 좋겠지만, 돌발 상황을 대비하여 모든 경우를 고려하려고 합니다. 당신의 목표는 가능한 모든 이익의 중간값을 찾는 것입니다. 즉, 우물을 팔 곳을 정하는 모든 $S=\frac{n(n-1)}{2}$가지 경우에 대해 얻을 수 있는 이익 중 $\lceil \frac{S}{2} \rceil$번째로 작은 것을 알아내려고 합니다. 이 문제를 해결하는 프로그램을 작성해 봅시다.

첫 줄에는 우물을 팔 수 있는 위치의 수 $N$이 주어집니다.

둘째 줄에는 각 위치에 우물을 팠을 때 얻을 수 있는 이익을 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 주어집니다.

가능한 모든 이익 중 $\lceil \frac{S}{2} \rceil$번째로 작은 값을 출력합니다.

• $2 \le N \le 50000$
• $1 \le A_i \le 10^9$