레몬 주스 게임

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

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

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

구사과는 레몬 주스로 만들 레몬의 즙의 양을 최대가 되게 게임을 할 것이고, 큐브러버는 즙의 양이 최소가 되게 게임을 할 것이다.

구사과는 이번 게임은 큐브러버를 속이고 진행하려고 한다. 게임 시작 전 큐브러버를 잠시 화장실에 보냈고, 그 사이 구사과는 레몬 k개를 미리 먹었다. 미리 먹는 레몬도 위에서 게임을 진행하는 것과 같이 결정을 하는 것이다. 큐브러버를 빼고 k번 턴을 먼저 진행하는 것과 같다.

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

첫째 줄에 레몬의 개수 N(1 ≤ N ≤ 300,000)이 주어진다.

둘째 줄에는 레몬 즙의 양 A1, A2, ..., AN(1 ≤ Ai ≤ 1,000,000,000)이 주어진다.

총 N개의 정수 b0, b1, ..., bn-1을 공백으로 구분해 출력한다. bi는 k = i일 때, 주스로 만드는 레몬 즙의 양이다.