Blokovi

~N~ ορθογώνια με δεδομένες μάζες (~m_i~) και ίσα μήκη (~2~) και ύψη (~h~) είναι διατεταγμένα σε καρτεσιανό επίπεδο έτσι ώστε:

• οι ακμές ορθογωνίου είναι παράλληλες με τους άξονες συντεταγμένων.
• οι συντεταγμένες y των κατώτερων οριζόντιων άκρων είναι διακριτές και λαμβάνουν τις ακόλουθες τιμές: ~0,\;h,\;2h,\;3h,\;\ldots\;,\;(N - 1)h~
• Η κάτω αριστερή γωνία του χαμηλότερου ορθογωνίου έχει συντεταγμένες ~(-2, 0)~, ενώ η κάτω δεξιά γωνία συμπίπτει με την αρχή.

Το κέντρο Χ ενός ορθογωνίου είναι η συντεταγμένη x του μέσου του κάτω άκρου του.
Το βαρυκέντρο Χ(Xbarycentre) ενός ή περισσότερων ορθογωνίων είναι ο σταθμισμένος μέσος όρος των κέντρων Χ τους. Υπολογίζεται ως

~Xbarycentre = \frac {\sum m_i \times Xcentre(i)} {\sum m_i} ~

Με άλλα λόγια, η μάζα κάθε ορθογωνίου πολλαπλασιάζεται με το Χ-κέντρο του και το άθροισμα αυτών των γινομένων διαιρείται στη συνέχεια με τη συνολική μάζα των ορθογωνίων.

Μια διάταξη είναι σταθερή εάν, για κάθε ορθογώνιο ~A~:

• το Χ-βαρύκεντρο των ορθογωνίων πάνω από το ~A~ έχει απόσταση το πολύ ~1~ από το κέντρο Χ του ~A~ (δηλαδή περιέχεται στο διάστημα x που καλύπτει το ~A~).

Διαισθητικά, η σταθερότητα μιας διάταξης μπορεί να γίνει κατανοητή ως η προϋπόθεση για να μην καταρρεύσει η διάταξη. Η διάταξη στο σχήμα στα αριστερά είναι ασταθής αφού το Χ-βαρυκέντρο των δύο κορυφαίων ορθογωνίων πέφτει έξω από το ορθογώνιο από κάτω (η απόσταση του βαρυκεντρικού Χ από το κέντρο Χ του υποκείμενου ορθογωνίου είναι μεγαλύτερη από 1). Η διάταξη στο σχήμα στα δεξιά είναι σταθερή.

Λαμβάνοντας υπόψη τις μάζες όλων των ορθογωνίων, βρείτε τη μεγαλύτερη ("δεξιά") δυνατή συντεταγμένη x από οποιαδήποτε γωνία ορθογωνίου σε σταθερή διάταξη. Δεν επιτρέπεται να αλλάξετε τη σειρά των ορθογωνίων (δίνονται από το χαμηλότερο στο υψηλότερο).

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(2 \leq N \leq 300\,000)~, τον αριθμό των ορθογωνίων.
Κάθε μία από τις επόμενες ~N~ γραμμές περιέχει έναν θετικό ακέραιο μικρότερο από ~10\,000~, τη μάζα ενός ορθογωνίου. Οι μάζες δίνονται κατά σειρά από το χαμηλότερο προς το υψηλότερο ορθογώνιο.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει την απαιτούμενη δεξιά συντεταγμένη x. Το δεδομένο αποτέλεσμα πρέπει να είναι εντός 0.000001 από την επίσημη λύση.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~30~% των πόντων, τα ορθογώνια θα ταξινομηθούν από το βαρύτερο στο ελαφρύτερο.

Παραδείγματα

input

2
1
1

output

1.000000

input

3
1
1
1

output

1.500000

input

3
1
1
9

output

1.900000