為了攢錢在牛棚裡建一個新的隔間，乳牛 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