8. Ale to sa oplatí!

Obchod Kde Sú Potraviny sa rohodol zaviesť bezpečnostné opatrenia proti rozsiahlemu postihnutiu políc prázdnotou. V KSP totiž zistili, že ľudia majú tendenciu prísť do obchodu s istým cieľom, a kúpiť si to čo chcú. Toto však vôbec nie je dobré. Keď príde veľa ludí s rovnakým cieľom, ostávajú prázdne police.

Zaviedli preto nový systém nakupovania. Zákazníkovi pridelia jednu policu ku ktorej sa postaví, podľa minuty od otvorenia v ktorej prišiel. Zákazník sa môže potom rozhodnúť, či to čo je na danej polici kúpi a odíde, alebo to nechce, hodí si mincou a posunie sa podľa nej doprava alebo doľava¹. Tý KSPáci sú ale kreatívny, že?

Marcela poslala jeho žena Sabinka do KSP nakupovať. Keďže vie o týchto opatreniach, nedala mu klasický nákupný zoznam, ale ku každej položke čo v obchode majú mu napísala, ako veľmi ju chce. Marcel sa pred cestou zamyslel, a uvedomil si, že ak vôjde v správnom čase, má väčšiu šancu kúpiť niečo, čo Sabinka chce viac. Ale kedy je ten správny čas?

Úloha

Na vstupe dostanete Sabinkino ohodnotenie všetkých vecí v obchode, zoradené tak, ako sú na policiach (na každej jedna vec). Vašou úlohou je zistiť, v ktorej minúte má Marcel prísť (teda na ktorej polici má začať svoj nákup), aby očakávaná hodnota toho čo kúpi bola čo najvyššia. Očakávaná hodnota sa dá vyrátať ako váhovaný priemer hodnoty podľa pravdepodobnosti, že Marcel kúpi jednotlivé veci. Môžete predpokladať, že v každom prípade by Marcel nechal svoj osud na náhodu, len ak by to zvíšilo jeho očakávaný zisk oproti tovau pri ktorom práve stojí. Aby sa Marcel vedel rozhodnúť aj keď niektorú minutu zmešká, vypíšte mu očakávaný zisk pre každú policu.

Formát vstupu

Na prvom riadku sa nachádza číslo \(n\), (\(1\leq n \leq 100\,000)\) počet políc v obchode. Na druhom riadku je \(n\) čísel, (\(0\leq x_i \leq 10^9\)), Sabinkino ohodnotenie jednotlivích políc s tovarom.

Formát výstupu

Vypíšte \(n\) riadkov, na \(i\)-tom z nich očakávanú hodnotu Marcelovho nákupu ak začne pri \(i\)-tej polici. Čísla vypisujte s presnosťou aspoň na 5 desatinných miest.

Príklad

Input:

2
1 3

Output:

1.5
3

Ak začne pri prvej polici, neoplatí sa mu zobrať daný tovar, lebo ak si hodí mincou má polovičnú šancu že vypadne a získa tak \(0\) ale polovičnú šancu skončiť na druhej polici a zobrať \(3\). To je v priemere \(1.5\), čo je viac ako \(1\).

Input:

6
2 3 6 13 4 1

Output:

3.25
6.5
9.75
13
8.66666
4.33333