밸런스 빔

소의 우리에 새 마구간을 지을 돈을 모으려고, 소 베시는 동네 서커스에서 공연을 시작했다. 높이 설치된 밸런스 빔 위에서 조심스럽게 왔다 갔다 하며 뛰어난 균형 감각을 보여 준다!

베시가 공연으로 버는 돈은 그녀가 최종적으로 빔에서 뛰어내리는 지점과 관련이 있다. 빔에는 왼쪽에서 오른쪽으로 $0, 1, \ldots, N+1$이라는 위치가 붙어 있다. 베시가 $0$이나 $N+1$에 도달하면 빔의 한쪽 끝에서 떨어져서 안타깝게도 아무 돈도 받지 못한다.

베시가 어떤 위치 $k$에 있을 때, 다음 두 가지 중 하나를 할 수 있다.

1. 동전을 던진다. 뒷면이 나오면 위치 $k-1$로, 앞면이 나오면 위치 $k+1$로 간다(즉, 각각 $\frac{1}{2}$의 확률).
2. 빔에서 뛰어내리고 $f(k)$ $(0 \leq f(k) \leq 10^9)$만큼의 돈을 받는다.

베시는 자신의 움직임이 무작위 동전 던지기에 따라 결정되므로 특정 지불 결과를 보장할 수 없다는 것을 알고 있다. 하지만 시작하는 위치를 기준으로, 최적의 결정 순서를 선택했을 때 기대 지불액이 얼마인지 알고 싶어 한다(여기서 "최적"이란 결정이 가능한 가장 높은 기대 지불액을 낳는다는 뜻이다). 예를 들어, 어떤 전략이 $10$을 확률 $1/2$로, $8$을 확률 $1/4$로, $0$을 확률 $1/4$로 받는다면, 기대 지불액은 가중 평균 $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$번째 줄에는 베시가 위치 $i$에서 시작해 최적으로 행동할 때의 기대 지불액에 $10^5$을 곱한 값을 내림하여 정수로 출력한다.