레몬 주스 게임

구사과와 큐브러버가 레몬 주스 게임을 하려고 한다.

레몬 주스 게임은 레몬 $N$개를 일렬로 놓고 진행하는 게임이다. $i$번째 레몬의 즙의 양은 $A_i$이다. 구사과는 레몬과 레몬 주스를 좋아하기 때문에 레몬 주스의 즙이 많은 것을 좋아하고, 큐브러버는 즙이 적은 것을 좋아한다.

오늘은 게임을 통해 주스로 만들 레몬을 정하려고 한다. 게임은 두 사람이 턴을 번갈아 가지며, 구사과가 먼저 시작한다. 각 턴에서 사람은 가장 앞이나 뒤에 있는 레몬을 하나 골라 먹는다. 레몬이 하나 남으면 게임이 끝나고, 이 레몬으로 레몬 주스를 만든다.

구사과는 레몬 주스의 즙의 양이 최대가 되도록 게임을 하고, 큐브러버는 즙의 양이 최소가 되도록 게임을 한다.

이번 게임에서 구사과는 큐브러버를 속이려고 한다. 게임을 시작하기 전에 구사과가 큐브러버를 잠시 화장실에 보내고, 그 사이에 구사과가 레몬 $k$개를 미리 먹는다. 미리 먹는 레몬도 게임과 같은 방식으로 고른다. 즉, 큐브러버 없이 구사과가 $k$번 턴을 먼저 진행하는 것과 같다.

각각의 $k$ ($0 \le k \le N-1$)에 대해, 두 사람이 최적의 방법으로 게임을 했을 때 레몬 주스를 만드는 레몬의 즙의 양을 구하는 프로그램을 작성하시오.

첫째 줄에 레몬의 개수 $N$ ($1 \le N \le 300{,}000$)이 주어진다.

둘째 줄에는 레몬 즙의 양 $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 1{,}000{,}000{,}000$)이 주어진다.

총 $N$개의 정수 $b_0, b_1, \ldots, b_{N-1}$을 공백으로 구분해 출력한다. $b_i$는 $k = i$일 때, 주스로 만드는 레몬 즙의 양이다.