### 问题描述 小齐正在马戏团表演，她站在一个标有位置 $0, 1, \ldots, N+1$ 的平衡木上。如果小齐达到位置 $0$ 或 $N+1$，她将会从平衡木的一端掉下，无法获得任何报酬。 在每个位置 $k$，小齐有两个选择： 投掷一枚硬币。如果是正面，她移动到位置 $k+1$，如果是反面，她移动到位置 $k-1$。 跳下平衡木，获得报酬 $f(k)$。 小齐希望基于她的起始位置确定她的期望报酬，假设她采取最优策略（"最优"意味着决策导致最高的期望报酬）。例如，如果她的策略以 $1/2$ 的概率获得 $10$，以 $1/4$ 的概率获得 $8$，以 $1/4$ 的概率获得 $0$，那么她的期望报酬将是加权平均值 $10(1/2) + 8(1/4) + 0(1/4) = 7$。 ### 输入格式 第一行包含一个整数 $N$。接下来的 $N$ 行，每行包含一个整数 $f(k)$。 ### 输出格式 输出 $N$ 行。第 $i$ 行输出小齐从位置 $i$ 开始并采取最优策略时的期望报酬，结果向下取整到最接近的整数。 ### 样例输入 ``` 2 1 3 ``` ### 样例输出 ``` 150000 300000 ``` ### 评测数据规模 $0 \leq f(k) \leq 10^9$，$2 \leq N \leq 10^5$。