为了攒钱在牛棚里建一个新的隔间，奶牛 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