Để dành tiền cho một ô chuồng mới trong chuồng của mình, cô bò Bessie đã bắt đầu biểu diễn tại rạp xiếc địa phương, thể hiện khả năng giữ thăng bằng đáng kinh ngạc khi cẩn thận đi qua lại trên một thanh thăng bằng ở trên cao!

Số tiền Bessie kiếm được từ màn biểu diễn phụ thuộc vào vị trí mà cuối cùng cô nhảy khỏi thanh. Các vị trí trên thanh được đánh số $0, 1, \ldots, N+1$ từ trái sang phải. Nếu Bessie đến vị trí $0$ hoặc $N+1$, cô sẽ rơi khỏi một trong hai đầu thanh và đáng tiếc là không nhận được tiền.

Nếu Bessie đang ở vị trí $k$, cô có thể thực hiện một trong hai hành động sau:

1. Tung một đồng xu. Nếu đồng xu ra mặt sấp, cô đi đến vị trí $k-1$; nếu ra mặt ngửa, cô đi đến vị trí $k + 1$ (tức là mỗi khả năng có xác suất $\frac{1}{2}$).
2. Nhảy khỏi thanh và nhận số tiền $f(k)$ $(0 \leq f(k) \leq 10^9)$.

Bessie nhận ra rằng cô có thể không đảm bảo được một khoản tiền cụ thể, vì chuyển động của cô phụ thuộc vào những lần tung đồng xu ngẫu nhiên. Tuy nhiên, với mỗi vị trí xuất phát, cô muốn xác định số tiền kỳ vọng mà mình sẽ nhận được nếu đưa ra một chuỗi quyết định tối ưu ("tối ưu" nghĩa là các quyết định dẫn đến số tiền kỳ vọng lớn nhất có thể). Ví dụ, nếu chiến lược của cô giúp cô nhận $10$ với xác suất $1/2$, $8$ với xác suất $1/4$, hoặc $0$ với xác suất $1/4$, thì số tiền kỳ vọng là trung bình có trọng số $10(1/2) + 8(1/4) + 0(1/4) = 7$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \leq N \leq 10^5$). $N$ dòng còn lại lần lượt chứa $f(1) \ldots f(N)$.

Dữ liệu ra

In ra $N$ dòng. Trên dòng $i$, in ra $10^5$ lần số tiền kỳ vọng nếu Bessie bắt đầu ở vị trí $i$ và đưa ra các quyết định tối ưu, làm tròn xuống số nguyên gần nhất.

Ví dụ

Dữ liệu vào 1

2
1
3

Dữ liệu ra 1

150000
300000

Tác giả bài toán: Franklyn Wang và Spencer Compton