A6419 | 「USACO 2018.12 Platinum」Balance Beam

**题目来自 [USACO 2018 December Contest, Platinum](http://usaco.org/index.php?page=dec18results) Problem 1. [Balance Beam](http://usaco.org/index.php?page=viewproblem2&cpid=864)**

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\le f(k)\le 10^9$）。

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

输入的第一行包含 $N$（$2\le N\le 10^5$）。

以下 $N$ 行包含 $f(1),\ldots,f(N)$。

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