Vous participez à un match de type « lockout ». Les règles sont simples : il s'agit d'un concours en 1 contre 1, comportant $n$ problèmes avec différents points attribués. Seul le premier participant à faire accepter le problème obtient les points ; même si l'autre est en retard d'une seconde, il n'obtient aucun point. Pour simplifier, nous n'inclurons pas de limites de temps ni de victoires anticipées : le match se poursuit jusqu'à ce que chaque problème soit résolu par au moins l'un des participants.

Vous êtes plutôt bon, mais... vous affrontez tourist. C'est un désastre, je sais. Il serait difficile de gagner, mais vous espérez arracher quelques points pour sauver les apparences. Si vous et tourist travaillez sur le même problème, il vous battra, c'est certain. Mais si vous avez choisi un problème différent, c'est votre chance ! Vous serez capable de résoudre ce problème avant tourist ! Mais ensuite, il entrera en mode « berserk » et résoudra instantanément tous les problèmes restants. Un problème vaut mieux que rien, n'est-ce pas ?

Formalisons un peu le processus. À chaque étape, vous et tourist avez des problèmes non résolus parmi lesquels choisir. S'il ne reste aucun problème non résolu, le jeu se termine et vous obtenez 0 point. Sinon, vous et tourist choisissez chacun un problème sur lequel travailler, sans savoir quel problème l'autre personne a choisi. Si vous choisissez le même problème, tourist le résout avant vous et nous revenons au même état initial avec moins de problèmes restants. Sinon, vous obtenez les points du problème que vous avez choisi, mais le jeu se termine immédiatement car tourist résout instantanément tous les problèmes restants.

Vous voulez maximiser le nombre de points que vous obtiendrez, tourist veut le minimiser. Quel est le résultat attendu du jeu si vous et tourist jouez de manière optimale ?

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 22$) — le nombre de problèmes. La deuxième ligne contient $n$ entiers $a_i$ ($1 \le a_i \le 10^9$) — les points pour chaque problème.

Sortie

Affichez un nombre — votre score attendu.

Votre réponse est considérée comme correcte si son erreur absolue ou relative n'excède pas $10^{-6}$. Formellement, soit $a$ votre réponse et $b$ la réponse du jury. Votre réponse est acceptée si et seulement si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Exemples

Entrée 1

2
6 7

Sortie 1

3.2307692307692

Entrée 2

3
1 1 1

Sortie 2

0.8333333333333

Entrée 3

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

Sortie 3

9.4422713866103

Remarque

Notez que dans le premier exemple, tourist pourrait sûrement gagner le match en choisissant toujours le deuxième problème, et contre cette stratégie, vous pourriez toujours choisir le premier problème et obtenir 6 points. Mais tourist jouera de manière optimale pour minimiser votre score attendu, ce qui pourrait parfois signifier vous laisser gagner le match.