Du spielst ein Lockout-Match. Die Regeln sind einfach: Es ist ein Duell, es gibt $n$ Aufgaben mit verschiedenen Punktzahlen, und nur der Teilnehmer, der eine Aufgabe zuerst erfolgreich löst, bekommt die Punkte. Selbst wenn der andere nur eine Sekunde später fertig wird, erhält er keine Punkte. Der Einfachheit halber gibt es weder ein Zeitlimit noch vorzeitige Siege: Das Match geht weiter, bis jede Aufgabe von mindestens einem Teilnehmer gelöst wurde.

Du bist ziemlich gut, aber ... dein Gegner ist tourist. Eine Katastrophe, ich weiß. Ein Sieg wird schwer, aber du hoffst, wenigstens ein paar Punkte zu ergattern, um dein Gesicht zu wahren. Wenn du und tourist an derselben Aufgabe arbeiten, wird er dich natürlich schlagen. Aber wenn du eine andere Aufgabe gewählt hast, ist das deine Chance! Diese Aufgabe kannst du vor tourist lösen! Dann allerdings schaltet er in den Berserkermodus und löst sofort alle verbleibenden Aufgaben. Eine Aufgabe ist besser als nichts, oder?

Formalisieren wir den Ablauf etwas. Jedes Mal stehen dir und tourist einige ungelöste Aufgaben zur Auswahl. Gibt es keine mehr, endet das Spiel, und du erhältst $0$ Punkte. Andernfalls wählt ihr beide eine Aufgabe aus, ohne die Wahl des anderen zu kennen. Wählt ihr dieselbe Aufgabe, löst tourist sie vor dir, und wir kehren mit weniger verbleibenden Aufgaben zum gleichen Ausgangszustand zurück. Andernfalls erhältst du die Punkte für die von dir gewählte Aufgabe, doch das Spiel endet sofort, weil tourist alle übrigen Aufgaben augenblicklich löst.

Du möchtest deine Punktzahl maximieren, tourist möchte sie minimieren. Wie groß ist der Erwartungswert des Spielergebnisses, wenn ihr beide optimal handelt?

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 22$) — die Anzahl der Aufgaben.

Die zweite Zeile enthält $n$ ganze Zahlen $a_i$ ($1 \le a_i \le 10^9$) — die Punktzahlen der einzelnen Aufgaben.

Ausgabe

Gib eine Zahl aus — den Erwartungswert deiner Punktzahl.

Deine Antwort gilt als korrekt, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet.

Formal seien $a$ deine Antwort und $b$ die Antwort der Jury. Deine Antwort wird genau dann akzeptiert, wenn $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ gilt.

Beispiele

Eingabe 1

2
6 7

Ausgabe 1

3.2307692307692

Eingabe 2

3
1 1 1

Ausgabe 2

0.8333333333333

Eingabe 3

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

Ausgabe 3

9.4422713866103

Hinweis

Beachte, dass tourist im ersten Beispiel das Match sicher gewinnen könnte, indem er stets die zweite Aufgabe wählt. Gegen diese Strategie könntest du immer die erste Aufgabe wählen und $6$ Punkte erhalten. Doch tourist spielt optimal, um den Erwartungswert deiner Punktzahl zu minimieren, was manchmal bedeuten kann, dass er dich das Match gewinnen lässt.