Per risparmiare denaro per un nuovo box nella sua stalla, la mucca Bessie ha iniziato a esibirsi nel circo locale, dimostrando il suo straordinario senso dell'equilibrio mentre cammina con attenzione avanti e indietro su una trave di equilibrio sopraelevata!

La quantità di denaro che Bessie guadagna durante la sua esibizione dipende dal punto in cui alla fine riesce a saltare giù dalla trave. Le posizioni della trave sono numerate $0, 1, \ldots, N+1$ da sinistra a destra. Se Bessie raggiunge $0$ o $N+1$, cade da una delle estremità della trave e, purtroppo, non riceve alcun pagamento.

Se Bessie si trova in una posizione $k$, può fare una delle seguenti cose:

1. Lanciare una moneta. Se esce croce, si sposta alla posizione $k-1$; se esce testa, si sposta alla posizione $k + 1$ (ciascun esito ha quindi probabilità $\frac{1}{2}$).
2. Saltare giù dalla trave e ricevere un pagamento di $f(k)$ $(0 \leq f(k) \leq 10^9)$.

Bessie si rende conto che potrebbe non riuscire a garantire un particolare pagamento, poiché i suoi movimenti dipendono dai lanci casuali della moneta. Tuttavia, in base alla posizione da cui parte, vuole determinare quale sarà il suo pagamento atteso se prende una sequenza ottimale di decisioni (dove «ottimale» significa che le decisioni portano al pagamento atteso più alto possibile). Per esempio, se la sua strategia le procura un pagamento di $10$ con probabilità $1/2$, di $8$ con probabilità $1/4$ oppure di $0$ con probabilità $1/4$, il suo pagamento atteso sarà la media ponderata $10(1/2) + 8(1/4) + 0(1/4) = 7$.

Formato dell'input

La prima riga dell'input contiene $N$ ($2 \leq N \leq 10^5$). Le restanti $N$ righe contengono rispettivamente $f(1) \ldots f(N)$.

Formato dell'output

Scrivi $N$ righe. Sulla riga $i$, scrivi $10^5$ volte il valore atteso del pagamento se Bessie parte dalla posizione $i$ e gioca in modo ottimale, arrotondato per difetto all'intero più vicino.

Esempi

Input 1

2
1
3

Output 1

150000
300000

Autori del problema: Franklyn Wang e Spencer Compton