좌석

좌석 게임에는 좌석 $n$개와 플레이어 $n$명이 있다. $i$번째 좌석에는 처음에 상금 $a_i$달러가 놓여 있다. 이 상금은 $i$번째 좌석을 차지하는 플레이어가 가져간다.

게임이 시작되기 전에 각 플레이어는 앉고 싶은 좌석 하나를 고른다. 게임이 시작되면 모든 플레이어가 자신이 고른 좌석을 향해 달려가서 그 좌석을 두고 다툰다. 어떤 좌석을 두고 다투는 플레이어들은 모두 같은 확률로 그 좌석에 앉아 상금을 가져간다고 가정한다. 다툼이 끝나면 그중 정확히 한 명이 그 좌석을 차지한다. 자신이 고른 좌석을 차지하지 못한 플레이어는 아무것도 얻지 못한다.

모든 플레이어가 동일한 고정 확률분포에서 자신의 좌석을 뽑는다고 하자. 이 분포를 최적으로 고를 때 플레이어 한 명이 얻는 기대 상금의 최댓값은 얼마인가?

다음 예를 보자. $n=2$, $a_1=1$, $a_2=2$라 하자. 모든 플레이어가 "더 이득인" 좌석 $2$를 확률 $1$로 고르기로 하면 각자의 기대 상금은 $\frac{1}{2}\cdot 2=1$달러이다. 그러나 좌석 $1$과 $2$에 각각 확률 $\frac{1}{3}$과 $\frac{2}{3}$을 배정하면 각 플레이어는 기대값으로 $\frac{7}{6}$달러를 얻는다.

첫째 줄에 정수 $n$이 주어진다 ($1\leq n\leq 5000$). 둘째 줄에 $n$개의 정수 $a_1,\ldots,a_n$이 주어진다 ($1\leq a_i\leq 1000$). 이는 각 좌석에 배정된 상금을 나타낸다.

확률분포를 최적으로 고를 때 플레이어 한 명이 얻는 기대 상금을 출력한다. 절대 오차 또는 상대 오차가 $10^{-7}$ 이하이면 정답으로 인정된다.