Để dành tiền xây một ô chuồng mới trong chuồng bò của mình, cô bò Bessie đã bắt đầu biểu diễn tại rạp xiếc địa phương, phô diễn khả năng giữ thăng bằng đáng kinh ngạc khi cẩn thận đi qua đi 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ô có thể 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 đi đến vị trí \(0\) hoặc \(N+1\), cô sẽ rơi khỏi một đầu thanh và đáng tiếc không nhận được khoản tiền nào.

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

1. Tung đồng xu. Nếu 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 mỗi khả năng xảy ra với xác suất \(\frac{1}{2}\)).

2. Nhảy khỏi thanh và nhận khoản 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ể nào vì chuyển động của cô bị chi phối bởi những lần tung đồng xu ngẫu nhiên. Tuy nhiên, dựa trên vị trí xuất phát, cô muốn xác định kỳ vọng số tiền 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 kỳ vọng số tiền cao nhất có thể). Ví dụ, nếu chiến lược của cô mang lại khoản tiền \(10\) với xác suất \(1/2\), khoản tiền \(8\) với xác suất \(1/4\), hoặc \(0\) với xác suất \(1/4\), thì kỳ vọng số tiền của cô 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)\), mỗi dòng một giá trị.

Dữ liệu ra

In ra \(N\) dòng. Trên dòng \(i\), in ra \(10^5\) lần kỳ vọng số tiền Bessie nhận được nếu cô xuất phát tại vị trí \(i\) và chơi tối ưu, được làm tròn xuống số nguyên gần nhất.

Ví dụ

2
1
3

150000
300000

Nguồn

Đề bài gốc: USACO 2018 December Contest, Platinum — Balance Beam

Tác giả: Franklyn Wang and Spencer Compton