Rozgrywasz mecz typu „lockout”. Zasady są proste: jest to pojedynek 1 na 1, w którym dostępnych jest $n$ zadań o różnych wartościach punktowych. Tylko pierwszy uczestnik, który uzyska akceptację zadania, otrzymuje punkty; nawet jeśli drugi uczestnik prześle rozwiązanie sekundę później, nie otrzymuje żadnych punktów. Dla uproszczenia pomijamy limity czasowe i wcześniejsze zakończenia: mecz trwa, dopóki każde zadanie nie zostanie rozwiązane przez przynajmniej jednego z uczestników.

Jesteś całkiem dobry, ale... mierzysz się z touristem. To katastrofa, wiem. Trudno będzie wygrać, ale masz nadzieję zdobyć choć trochę punktów, żeby zachować twarz. Jeśli ty i tourist będziecie pracować nad tym samym zadaniem, on na pewno cię pokona. Ale jeśli wybierzesz inne zadanie, masz szansę! Będziesz w stanie rozwiązać to zadanie przed touristem! Jednak wtedy on wejdzie w tryb „berserk” i natychmiast rozwiąże wszystkie pozostałe zadania. Jedno zadanie to zawsze lepiej niż nic, prawda?

Sformalizujmy nieco ten proces. W każdej chwili ty i tourist macie do wyboru pewien zestaw nierozwiązanych zadań. Jeśli nie pozostały żadne nierozwiązane zadania, gra kończy się i otrzymujesz 0 punktów. W przeciwnym razie zarówno ty, jak i tourist wybieracie zadanie, nad którym będziecie pracować, nie wiedząc, jakie zadanie wybrała druga osoba. Jeśli wybierzecie to samo zadanie, tourist rozwiąże je przed tobą i wracamy do tego samego stanu początkowego z mniejszą liczbą pozostałych zadań. W przeciwnym razie otrzymujesz punkty za zadanie, które wybrałeś, ale gra natychmiast się kończy, ponieważ tourist błyskawicznie rozwiązuje wszystkie pozostałe zadania.

Chcesz zmaksymalizować liczbę punktów, które zdobędziesz, a tourist chce ją zminimalizować. Jaki jest oczekiwany wynik gry, jeśli zarówno ty, jak i tourist postępujecie optymalnie?

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 22$) — liczbę zadań. Druga linia zawiera $n$ liczb całkowitych $a_i$ ($1 \le a_i \le 10^9$) — punkty za każde zadanie.

Wyjście

Wypisz jedną liczbę — twój oczekiwany wynik.

Twoja odpowiedź jest uznawana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekracza $10^{-6}$. Formalnie, niech twoja odpowiedź wynosi $a$, a odpowiedź jury $b$. Twoja odpowiedź jest zaakceptowana wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1, |b|)} \le 10^{-6}$.

Przykład

Wejście 1

2
6 7

Wyjście 1

3.2307692307692

Wejście 2

3
1 1 1

Wyjście 2

0.8333333333333

Wejście 3

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

Wyjście 3

9.4422713866103

Uwagi

Zauważ, że w pierwszym przykładzie tourist mógłby z pewnością wygrać mecz, zawsze wybierając drugie zadanie, a przeciwko tej strategii mógłbyś zawsze wybrać pierwsze zadanie i zdobyć 6 punktów. Jednak tourist będzie grał optymalnie, aby zminimalizować twój oczekiwany wynik, co czasami może oznaczać pozwolenie ci na wygranie meczu.