우물 파기

폴리매스 왕국의 사람들은 우물에서 지하수를 길어 마신다. 지하수의 근원은 물의 돌이라고 알려져 있지만, 물의 돌이 정확히 어디에 있는지 아는 사람은 아무도 없다.

최근 인구가 늘면서 물이 부족해졌다. 사람들은 이 문제를 해결하려고 우물 두 개를 더 파기로 했다. 우물을 팔 수 있는 곳은 $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$