케이크 Batch 컴파일 명령

석환이와 상수는 S대학 동문입니다. 석환이는 최근 제과제빵학원에 다니며 과자와 빵 만들기에 열중하고 있습니다. 오늘도 석환이는 케이크를 만들어 먹으려고 했는데, 상수가 맛있는 냄새를 따라 주방에 왔기 때문에, 두 사람이 케이크를 나눠 먹게 되었습니다.

케이크는 원 모양입니다. 석환이는 특정 지점에서 직선을 몇 개 그어 케이크를 N개의 조각으로 나눴고, 각 조각에 1 이상 N 이하의 자연수 번호를 시계 반대 방향으로 붙였습니다. 즉 1 ≤ i ≤ N을 만족하는 모든 i에 대해, i번 조각은 (i - 1)번 조각, (i + 1)번 조각과 붙어 있습니다. (단 0번 조각은 N번 조각으로, (N + 1)번 조각은 1번 조각으로 간주합니다.) i번 조각의 크기는 A_i입니다. 석환이는 케이크 자르는 솜씨가 매우 서투르기 때문에, 각 조각의 크기, 즉 A_i는 서로 다릅니다.

<small>그림 1: 케이크의 예 (N = 5, A₁ = 2, A₂ = 8, A₃ = 1, A₄ = 10, A₅ = 9)</small>

석환이와 상수는 케이크 N조각을 서로 나누어 가지기로 했습니다. 나누는 방법은 아래와 같습니다:

• 우선 석환이가 N조각 중 하나를 선택하여 가져갑니다.
• 이후 상수부터 시작해서 두 사람은 번갈아 가면서 케이크 한 조각을 가져갑니다. 두 조각 사이에 있는 조각을 가져가면 케이크의 모양이 흐트러질 우려가 있으므로, 조각들 중 좌우 양쪽의 조각 중 적어도 한 쪽이 집혀 간 조각만 집어 갈 수 있고, 그런 조각이 여러 개 있을 때에는 가장 큰 것을 집습니다.

석환이는, 각 조각에 대해, 그 조각을 자신이 가장 먼저 가져갔을 때, 자신이 최종적으로 가져갈 케이크 조각들의 크기의 합이 얼마인지 알고자 합니다

해야 할 일

케이크 조각의 수 N과, N개의 조각의 크기의 정보가 주어졌을 때, 각 조각에 대해, 석환이가 그 조각을 가장 먼저 가져갔을 때, 석환이가 최종적으로 가져갈 케이크 조각들의 크기의 합을 구하는 프로그램을 작성하세요.

입력 형식

• 첫 번째 줄에 정수 N이 주어집니다. 이는 케이크가 N개의 조각들로 분리되어 있음을 나타냅니다.
• 이후 N개의 줄이 주어지는데, 이 중 i번째 줄 (1 ≤ i ≤ N)에는 정수 A_i가 주어집니다. 이는 i번 조각의 크기가 A_i라는 것을 나타냅니다.

출력 형식

N개의 줄을 출력합니다. 이 중 i (1 ≤ i ≤ N)번째 줄에는, 석환이가 i번 조각을 가장 먼저 가져갔을 때, 석환이가 최종적으로 가져갈 케이크 조각들의 크기의 합을 나타내는 정수 하나를 출력해야 합니다.

제약 조건

모든 입력 데이터는 아래 조건을 만족합니다.

• 2 ≤ N ≤ 300 000
• 1 ≤ A_i ≤ 1 000 000 000 (1 ≤ i ≤ N)

부분문제

부분문제 1 (10점)

• 2 ≤ N ≤ 5 000

부분문제 2 (90점)

추가 제약 조건이 없습니다.

예제

이 예는 문제 문중의 그림의 예로 대응하고 있다.

이 예제는 위 [그림 1]과 같습니다.

석환이가 1번 조각을 처음 가져갔다고 합시다. 이 때,

• 남아 있는 조각들 중 "좌우 양쪽의 조각 중 적어도 한 쪽 조각이 집혀 간" 조각은 2번 조각과 5번 조각입니다. 5번 조각이 크므로 상수는 5번 조각을 가져갑니다.
• 그 다음, 2번 조각과 4번 조각을 가져갈 수 있고, 이 중 4번 조각이 크므로, 석환이는 4번 조각을 가져갑니다.
• 그 다음, 2번 조각과 3번 조각을 가져갈 수 있고, 이 중 2번 조각이 크므로, 상수는 2번 조각을 가져갑니다.
• 마지막에는 3번 조각만 남아 있으므로 석환이가 3번 조각을 가져갑니다.

즉 조각을 가져가는 순서는

• 1번 조각 (크기 2) → 5번 조각 (크기 9) → 4번 조각 (크기 10) → 2번 조각 (크기 8) → 3번 조각 (크기 1)

석환이가 가져간 조각들은 1번, 4번, 3번 조각으로, 크기의 합은 13이므로, 첫 번째 줄에 13을 출력해야 합니다.