题目描述

Bessie为了存钱给她的牛棚新建一间隔间，开始在当地的马戏团里表演，通过在平衡木上小心地来回走动来展示她卓越的平衡能力。

Bessie能够通过表演赚到的钱取决于她最终成功跳下平衡木的位置。平衡木上从左向右的位置记为 $0,1,\ldots,N+1$ 。如果Bessie到达了位置 $0$ 或是 $N+1$ ，她就会从平衡木的一端掉下去，遗憾地得不到报酬。

如果Bessie处在一个给定的位置 $k$ ，她可以进行下面两项中的任意一项：

1. 投掷一枚硬币。如果背面朝上，她前往位置 $k-1$ ，如果正面朝上，她前往位置 $k+1$ （也就是说，每种可能性 $1/2$ 的概率）。

2. 跳下平衡木，获得 $f(k)$ 的报酬（ $0 \leq f(k) \leq 10^9$ ）。

Bessie意识到她并不能保证结果能够得到某一特定数量的报酬，这是由于她的移动是由随机的掷硬币结果控制。然而，基于她的起始位置，她想要求出当她进行一系列最优的决定之后，她能够得到的期望报酬（“最优”指的是这些决定能够带来最高可能的期望报酬）。

例如，如果她的策略能够使她以 $1/2$ 的概率获得 $10$ 的报酬，$1/4$ 的概率获得 $8$ 的报酬，$1/4$ 的概率获得 $0$ 的报酬，那么她的期望报酬为加权平均值 $10 \times (1/2)+8 \times (1/4)+0 \times (1/4)=7$ 。

输入格式

输入的第一行包含 $N$ （ $2 \leq N \leq 10^5$ ）。以下 $N$ 行包含 $f(1) \ldots f(N)$ 。

输出格式

输出 $N$ 行。第 $i$ 行输出 $10^5$ 乘以Bessie从位置 $i$ 开始使用最优策略能够获得的报酬的期望值，向下取整。

2
1
3

150000
300000