Thanh Cân Bằng

Có một thanh cân bằng với $N+2$ vị trí được đánh số từ $0$ đến $N+1$. Vị trí $0$ và $N+1$ là hai đầu mút — nếu đến đó thì nhận được $0$ điểm thưởng.

Mỗi vị trí $k$ ($1\le k\le N$) có một giá trị thưởng $f(k)\ge 0$. Tại mỗi bước, khi đứng ở vị trí $k$, bạn có thể:

• Nhảy xuống tại chỗ và nhận $f(k)$ điểm thưởng, hoặc
• Tung đồng xu: với xác suất $1/2$ di chuyển sang trái (vị trí $k-1$), với xác suất $1/2$ di chuyển sang phải (vị trí $k+1$).

Mục tiêu là tối đa hóa kỳ vọng số điểm thưởng nhận được. Gọi $f^{*}(k)$ là kỳ vọng điểm thưởng tối ưu khi bắt đầu ở vị trí $k$.

Với mỗi vị trí $k$ từ $1$ đến $N$, hãy tính $\lfloor f^{*}(k)\times {10}^5\rfloor$.

Dữ liệu vào

• Dòng 1: số nguyên $N$ ($2\le N\le {10}^5$)
• $N$ dòng tiếp theo: giá trị $f(1),f(2),\dots ,f(N)$ ($0\le f(k)\le {10}^9$)

Dữ liệu ra

• $N$ dòng, dòng $k$ chứa $\lfloor f^{*}(k)\times {10}^5\rfloor$.

Ràng buộc

• $2\le N\le {10}^5$
• $0\le f(k)\le {10}^9$

Ví dụ