Problem description
Jan jest udziałowcem w firmie Log & Roll, zajmującej się sadzeniem i wycinką drzew. W tym roku firma planuje dobudowanie nowego magazynu na kłody ściętych drzew. Wszystkie kłody są tej samej długości, więc można je opisać za pomocą jednego parametru – ich promienia. Wiadomo już w jakiej kolejności kłody drewna będą umieszczane w magazynie. Każda z nich wturla się do magazynu od prawej strony i zatrzyma po zetknięciu z pierwszą przeszkodą (albo ścianą magazynu, albo z jakąś inną, będącą tam już wcześniej kłodą).
Jan jest bardzo zajęty innymi pracami wykonywanymi w firmie (podpisywaniem umów międzynarodowych, wypłatą wynagrodzeń pracownikom, graniem w Drwala…), więc poprosił Cię o napisanie programu, który wczyta parametry kolejnych kłód pojawiających się w magazynie, a na końcu wypisze minimalną długość dachu magazynu, która pozwoli na to, że każda kłoda znajdzie się w całości wewnątrz magazynu. Możesz założyć, że wysokość oraz szerokość ma gazynu mogą być dowolnie duże.
Ilustracja testu przykładowego, gdzie D to szukana długość dachu magazynu.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę kłód, które mają zostać pomieszczone w nowym magazynie. W drugim wierszu wejścia znajduje się N liczb naturalnych a1, a2, …, aN, oznaczających promienie kolejnych kłód.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę rzeczywistą D, oznaczającą szukaną długość dachu magazynu. Twoja odpowiedź zostanie uznana za poprawną, jeżeli błąd względny lub bezwzględny nie będzie większy niż 10−6.
Ograniczenia
1 ≤ N ≤ 3000, 1 ≤ ai ≤ 109.
Przykłady
| Wejście | Wyjście | |
|
|