케이크

JOI 군과 IOI 양은 쌍둥이 남매이다. 최근 JOI 군은 과자 만들기에 푹 빠져 있다. 오늘도 JOI 군은 케이크를 구워 먹으려 했는데, 막 다 구워졌을 때 냄새를 맡은 IOI 양이 와서 둘이 케이크를 나눠 먹게 되었다.

케이크는 원형이다. 한 점에서 방사형으로 칼집을 내어 케이크를 $N$개의 조각으로 자르고, 조각에 1번부터 $N$번까지 반시계 방향으로 번호를 붙였다. 즉, $1 \le i \le N$인 $i$번 조각은 $i-1$번 조각 및 $i+1$번 조각과 인접한다. 단, 0번 조각은 $N$번 조각으로, $N+1$번 조각은 1번 조각으로 본다. $i$번 조각의 크기는 $A_i$인데, 칼질이 서툴러서 모든 $A_i$가 서로 다른 값이 되었다.

그림 1: 케이크의 예 ($N = 5$, $A_1 = 2$, $A_2 = 8$, $A_3 = 1$, $A_4 = 10$, $A_5 = 9$)

JOI 군과 IOI 양은 이 $N$개의 조각을 다음 방식으로 나누기로 했다.

• 먼저 JOI 군이 $N$개 중 하나를 골라 가진다.
• 그다음 IOI 양부터 시작하여 IOI 양과 JOI 군이 번갈아 가며 남은 조각을 하나씩 가진다. 두 사람은 케이크를 부스러뜨리지 않으려고 조심하다 보니 잘 집지 못한다. 그래서 양옆 조각 중 적어도 하나가 이미 가져간 조각만 가질 수 있다. 가질 수 있는 조각이 여럿이면 그중 가장 큰 조각을 가진다.

JOI 군은 각 조각에 대해, 그 조각을 처음에 가졌을 때 자신이 최종적으로 가지게 되는 조각 크기의 합이 얼마인지 알고 싶어 한다.

표준 입력에서 다음 형식으로 입력이 주어진다.

$N$ $A_1$ $A_2$ $\vdots$ $A_N$

• 첫 줄에는 정수 $N$이 주어지며, 케이크가 $N$개의 조각으로 나뉘어 있음을 뜻한다.
• 이어지는 $N$줄 중 $i$번째 줄 ($1 \le i \le N$)에는 정수 $A_i$가 주어지며, $i$번 조각의 크기가 $A_i$임을 뜻한다.

표준 출력에 $N$줄을 출력한다. $i$번째 줄 ($1 \le i \le N$)에는 $i$번 조각을 처음에 가졌을 때 JOI 군이 최종적으로 가지게 되는 조각 크기의 합을 정수 하나로 출력한다.

• $2 \le N \le 300\,000$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• 모든 $A_i$는 서로 다르다.