번갈아 고르기

농부 John이 소들에게 먹이를 주는 새로운 방법을 고안했다. 그는 헛간에 건초 더미 $N$개($1 \le N \le 700000$)를 한 줄로 길게 늘어놓고 $1 \ldots N$번으로 번호를 매긴다. $i$번 건초 더미의 무게는 $W_i$($1 \le W_i \le 2000000000$)이다. 예를 들어 여섯 개의 무게가 다음과 같이 놓일 수 있다.

17 5 9 10 3 8

Bessie와 Dessie라는 두 소가 모든 건초 더미의 무게를 확인한 뒤 줄을 따라 걸어 내려간다. Bessie가 먼저 고른다. 두 소는 걸어가면서 번갈아 가며 먹을 건초 더미를 고르는데, 한 번 지나친 건초 더미는 다시 고를 수 없다. 예를 들어 한 가지 진행은 다음과 같을 수 있다.

• Bessie가 무게 $17$인 더미를 고른다.
• Dessie가 무게 $5$인 더미를 건너뛰고 무게 $9$인 더미를 고른다.
• Bessie가 무게 $10$인 더미를 고른다.
• Dessie가 무게 $3$인 더미를 건너뛰고 무게 $8$인 더미를 고른다.

그림으로 나타내면 다음과 같다.

Bessie   |      |
        17 5 9 10 3 8
Dessie       |      |

이 진행에서는 한 번에 한 개씩만 건너뛰었지만, 자기 차례에 소는 원하는 만큼 여러 더미를 건너뛸 수 있다.

각 소는 자신이 먹는 건초의 총 무게를 최대로 만들고자 하며, 상대도 같은 목표를 가진다는 사실을 서로 알고 있다. 또한 선택의 여지가 있을 때, 소는 자신의 최대 총합을 달성하는 가장 앞쪽(왼쪽) 더미를 먹는다.

건초 무게의 수열이 주어질 때, 두 소가 줄을 따라 내려가며 각각 먹게 되는 건초의 양을 구하라.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$번째 줄까지: $i+1$번째 줄에 정수 $W_i$가 하나씩 주어진다.

• 첫째 줄: 두 정수를 공백으로 구분하여 출력한다. 각각 Bessie와 Dessie가 먹은 건초의 총 무게이다.