당신은 락아웃(lockout) 매치를 하고 있습니다. 규칙은 간단합니다. 1대1 대결이며, 다양한 점수가 배정된 $n$개의 문제가 있습니다. 오직 문제를 먼저 맞힌 참가자만이 점수를 얻으며, 상대방보다 1초라도 늦게 맞히면 점수를 얻지 못합니다. 단순화를 위해 시간 제한이나 조기 승리 규칙은 고려하지 않습니다. 매치는 모든 문제가 적어도 한 명의 참가자에 의해 해결될 때까지 계속됩니다.

당신은 꽤 실력이 좋지만, 상대는 tourist입니다. 재앙이나 다름없죠. 이기기는 어렵겠지만, 체면을 살리기 위해 점수를 조금이라도 얻고 싶어 합니다. 만약 당신과 tourist가 같은 문제를 풀려고 한다면, 당연히 그가 당신을 이길 것입니다. 하지만 당신이 다른 문제를 선택한다면 기회가 있습니다! 당신은 tourist보다 먼저 그 문제를 해결할 수 있을 것입니다! 하지만 그 직후 그는 버서크 모드에 돌입하여 남은 모든 문제를 즉시 해결해 버릴 것입니다. 문제 하나라도 얻는 게 아무것도 없는 것보다는 낫지 않을까요?

이 과정을 조금 더 형식화해 보겠습니다. 매 순간 당신과 tourist는 해결되지 않은 문제들 중 하나를 선택해야 합니다. 해결되지 않은 문제가 남아있지 않으면 게임이 종료되고 당신은 0점을 얻습니다. 그렇지 않으면, 당신과 tourist는 상대방이 어떤 문제를 선택했는지 모르는 상태에서 각자 풀 문제를 선택합니다. 만약 같은 문제를 선택한다면, tourist가 당신보다 먼저 해결하고 우리는 문제가 줄어든 동일한 초기 상태로 돌아갑니다. 반대로 다른 문제를 선택한다면, 당신은 선택한 문제의 점수를 얻지만, tourist가 남은 모든 문제를 즉시 해결해 버리기 때문에 게임은 즉시 종료됩니다.

당신은 얻을 점수를 최대화하고 싶어 하고, tourist는 이를 최소화하고 싶어 합니다. 당신과 tourist가 모두 최적으로 행동할 때 게임의 기대 결과는 무엇입니까?

입력

첫 번째 줄에는 문제의 개수를 나타내는 정수 $n$ ($1 \le n \le 22$)이 주어집니다. 두 번째 줄에는 각 문제의 점수를 나타내는 $n$개의 정수 $a_i$ ($1 \le a_i \le 10^9$)가 주어집니다.

출력

당신의 기대 점수를 하나의 숫자로 출력하십시오. 당신의 답은 절대 오차나 상대 오차가 $10^{-6}$을 넘지 않으면 정답으로 간주됩니다. 공식적으로, 당신의 답을 $a$, 심사위원의 답을 $b$라고 할 때, $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$을 만족하면 정답으로 인정됩니다.

예제

입력 1

2
6 7

출력 1

3.2307692307692

입력 2

3
1 1 1

출력 2

0.8333333333333

입력 3

11
1 2 3 4 5 6 7 8 9 10 11

출력 3

9.4422713866103

참고

첫 번째 예제에서 tourist는 항상 두 번째 문제를 선택하여 확실하게 매치를 이길 수 있습니다. 그리고 이러한 전략에 대응하여 당신은 항상 첫 번째 문제를 선택하여 6점을 얻을 수 있습니다. 하지만 tourist는 당신의 기대 점수를 최소화하기 위해 최적으로 플레이할 것이며, 이는 때때로 당신이 매치에서 점수를 얻도록 허용하는 것을 의미할 수도 있습니다.