Problem 1. Balance Beam

USACO 2018 December Contest, Platinum

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

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

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

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

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

Bessie意识到她并不能保证结果能够得到某一特定数量的报酬，这是由于她的移动是由随机的掷硬币结果控制。然而，基于她的起始位置，她想要求出当她进行一系列最优的决定之后，她能够得到的期望报酬（“最优”指的是这些决定能够带来最高可能的期望报酬）。例如，如果她的策略能够使她以$1/2$的概率获得$10$的报酬，$1/4$的概率获得$8$的报酬，$1/4$的概率获得$0$的报酬，那么她的期望报酬为加权平均值$10(1/2) + 8(1/4) + 0(1/4) = 7$.

输入格式（文件名：balance.in）：

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

输出格式（文件名：balance.out）：

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

输入样例：

2
1
3

输出样例：

150000
300000

供题：Franklyn Wang and Spencer Compton