Runda 17 - Kulki w walcu

Zawody stałe, runda 17.

Limit czasowy: 7s; Limit pamięciowy: 32 MB

Kulki w walcu

Mamy daną długą rurkę (walec który jest pusty w środku). Rurka ta stoi na stole i jest otwarta z góry. Promień rurki to 1cm. Mamy też zestaw stalowych kulek. Chcemy wrzucić te kulki do środka rurki tak, by różnica wysokości między najniżej zajętym przez którąkolwiek kulkę punktem a najwyżej zajętym była minimalna. Kulki zawsze spadają maksymalnie w dół jak tylko jest to możliwe (przy wrzuceniu od góry). Innymi słowy chcemy, aby wysokość utworzonej w ten sposób wieży z kulek była jak najmniejsza. Promień kulki zawsze spełnia zależność 0.5 ≤ r ≤ 1.

Wejście

Pierwsza liczba, to 1≤t≤10, liczba przypadków testowych Kolejne t testów jest następującej postaci: Wpierw, 1≤n≤100000, liczba kulek. Kolejna linia zawiera n różnych liczb z przedziału (0.5,1], promieni dostępnych nam kulek.

Wyjście

Dla każdego przypadku testowego - dokładnie jedna liczba, najmniejsza wysokość jaką można uzyskać. Wynik wypisz z dokładnością do 6 cyfr po przecinku.

Przykład

Wejście:

1
3
1 0.7 0.9

Wyjście:

5.122513

Wyjaśnienie przykładu: gdy w walcu umieścimy najpierw kulkę o promieniu 1, potem o promieniu 0.7, a potem 0.9, uzyskamy najmniejszą wysokość.