为了攒钱在牛棚里添置一个新隔间，奶牛 Bessie 开始在当地马戏团表演。她小心翼翼地在高高的平衡木上来回行走，展示自己出色的平衡感！
Bessie 在表演中赚到的钱与她最终从平衡木上跳下的位置有关。平衡木上的位置从左到右标为 $0, 1, \ldots, N+1$。如果 Bessie 到达 $0$ 或 $N+1$，她就会从平衡木的一端掉下去，遗憾地拿不到任何报酬。
如果 Bessie 位于某个位置 $k$，她可以选择以下两种行动之一：
- 抛一枚硬币。如果反面朝上，她就走到位置 $k-1$；如果正面朝上，她就走到位置 $k + 1$（也就是说，两种情况发生的概率均为 $\frac{1}{2}$）。
- 跳下平衡木，获得 $f(k)$ 的报酬，其中 $(0 \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$。
输入格式
输入的第一行包含 $N$（$2 \leq N \leq 10^5$）。接下来的 $N$ 行分别包含 $f(1) \ldots f(N)$。
输出格式
输出 $N$ 行。在第 $i$ 行输出：如果 Bessie 从位置 $i$ 出发并采取最优策略，她获得的期望报酬乘以 $10^5$ 后向下取整所得的整数。
样例
输入格式 1
2
1
3输出格式 1
150000
300000题目作者：Franklyn Wang 和 Spencer Compton