Para ahorrar dinero y comprar un nuevo establo en su granero, la vaca Bessie ha comenzado a actuar en el circo local, demostrando su notable sentido del equilibrio al caminar con cuidado de un lado a otro sobre una viga de equilibrio elevada.

La cantidad de dinero que Bessie gana en su actuación depende de la posición desde la que finalmente decide saltar de la viga. La viga tiene posiciones etiquetadas como ~0, 1, ..., N+1~ de izquierda a derecha. Si Bessie llega a la posición ~0~ o a la ~N+1~, se cae por uno de los extremos de la viga y, lamentablemente, no recibe ningún pago.

Si Bessie se encuentra en una posición determinada ~k~, puede realizar una de las siguientes acciones:

1. Lanzar una moneda. Si sale cruz, se mueve a la posición ~k-1~; si sale cara, se mueve a la posición ~k+1~ (es decir, hay una probabilidad de ~1/2~ para cada caso).
2. Saltar de la viga y recibir un pago de ~f(k)~.

Bessie se da cuenta de que tal vez no pueda garantizar un resultado de pago específico, ya que su movimiento depende de lanzamientos aleatorios de moneda. Sin embargo, basándose en su posición inicial, quiere determinar cuál será su pago esperado si toma una secuencia óptima de decisiones (entendiendo por "óptima" aquella que conduce al mayor pago esperado posible). Por ejemplo, si su estrategia le reporta un pago de 10 con probabilidad ~1/2~, de 8 con probabilidad ~1/4~ o de 0 con probabilidad ~1/4~, entonces su pago esperado será el promedio ponderado: ~10(1/2) + 8(1/4) + 0(1/4) = 7~.

Entrada

La primera línea de la entrada contiene ~N~. Cada una de las ~N~ líneas restantes contiene los valores ~f(1)...f(N)~.

Salida

Imprime ~N~ líneas. En la línea ~i~, imprime el valor esperado del pago —multiplicado por ~10^5~— si Bessie comienza en la posición ~i~ y juega de manera óptima, redondeado hacia abajo al entero más cercano.

Restricciones

• ~2 \leq N \leq 10^5~
• ~0 \leq f(k) \leq 10^9~

Ejemplo de Entrada

2
1
3

Ejemplo de Salida

150000
300000

USACO 2018 December Contest, Platinum Problem 1. Balance Beam.