서커스 공연 알바

지민은 창업 자금을 모으기 위해, 현지 서커스에서 공연을 하기 시작했습니다.

지민이 공연에서 벌어 들이는 돈의 양은 그녀가 균형봉에서 어디에서 뛰어내리는지에 관련되어 있습니다. 균형봉에는 왼쪽에서 오른쪽으로 $0, 1, \ldots, N+1$까지의 위치가 표시되어 있습니다. 지민이 $0$ 또는 $N+1$에 닿으면 균형봉의 양 끝에서 떨어지고 아쉽게도 아무런 보상을 받지 못합니다.

지민이 주어진 위치 $k$에 있으면 다음 중 하나를 할 수 있습니다:

1. 동전을 던집니다. 만약 뒷면(tails)이 나오면, 그녀는 위치 $k-1$로 이동하고, 만약 앞면(heads)이 나오면 위치 $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$를 곱하고 가장 가까운 정수로 내림하여 출력합니다.