27066번 - 나무 블럭 게임 스페셜 저지

올해도 집에서 쓸쓸히 혼자 새해를 맞이하는 주원이는 제야의 종이 울리기 전까지 심심함을 달랠 무언가를 찾고 있다.

주원이는 근처에 굴러다니는 $N$개의 나무 블럭을 발견했다. 각 나무 블럭에는 음이 아닌 정수가 한 개씩 적혀있었다. 심심한 주원이는 나무 블럭들을 가지고 혼자서 할 수 있는 간단한 게임을 떠올렸다.

처음에 $N$개의 나무 블럭은 $N$개의 주머니에 한 개씩 들어있다. 이때 주원이는 다음 작업을 원하는 만큼 반복할 수 있다.

• 서로 다른 두 주머니를 고른 다음 둘을 하나로 합친다.

예를 들어, 첫 번째 주머니에 2가 적힌 나무 블럭과 5가 적힌 나무 블럭이, 두 번째 주머니에 3이 적힌 나무 블럭이 들어있다고 하자. 이 두 주머니를 합치면 각각 2, 3, 5가 적힌 나무 블럭 총 세 개가 하나의 주머니에 들어 있게 된다. 따라서 주머니의 총 개수는 하나 줄어든다.

게임의 모든 과정이 끝난 뒤 남아있는 주머니의 개수가 $K$개라고 할 때, 각각에 대해 들어있는 나무 블럭에 적힌 수의 평균을 구하자. 각 주머니에서 계산한 $K$개의 평균들을 오름차순으로 나열했을 때 $\left\lfloor\cfrac{K+1}{2}\right\rfloor$번째에 위치한 값이 주원이의 점수가 된다.

제야의 종이 울리기 전에 주원이가 게임을 마스터할 수 있도록 나무 블럭의 정보가 주어지면 얻을 수 있는 점수의 최댓값을 구해주는 프로그램을 만들어주자.

첫째 줄에 나무 블럭의 개수 $N$이 주어진다.

둘째 줄에 각 나무 블럭에 적혀있는 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

게임에서 얻을 수 있는 가장 큰 점수를 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.

• $1\leq N\leq 100\,000$
• $0\leq A_i\leq 10\,000$