활쏘기 대결

오늘도 평화로운 KSA 수업 시간에는 활쏘기 대결을 한다. 표적은 총 $N$개이다. 맨 위의 표적 하나는 고정되어 있고, 나머지는 한 줄로 하나씩 아래에 매달려 있다. 표적의 번호는 $1$부터 $N$까지 매겨져 있으며, 맨 위의 표적이 $1$번이다. $i$번 표적($1 < i \leq N$)은 $i-1$번 표적에 매달려 있고, $i$번 표적의 점수는 $A_i$이다.

두 플레이어가 번갈아 차례를 가진다. 자신의 차례에는 아래 두 가지 동작 중 하나를 선택할 수 있다.

• 표적 하나를 선택해 활을 쏴서 맞힌다.
• 기권한다.

표적을 맞히면 그 표적은 파괴되고, 표적의 점수는 맞힌 사람의 점수에 합산된다. 파괴된 표적 밑에 달려 있던 표적들은 바닥에 떨어진다. 떨어졌지만 파괴되지 않은 표적들의 점수는 상대방의 점수에 합산된다. 기권하면 파괴되지도 떨어지지도 않은 모든 표적의 점수가 상대방의 점수에 합산되고, 게임이 즉시 종료된다. 모든 표적이 파괴되거나 떨어진 경우에도 게임이 종료된다. 이번에 참가하는 두 학생은 명사수라서 선택한 표적을 반드시 맞힐 수 있고, 자신의 점수를 최대화하기 위해 최적의 선택만 한다. 게임 결과를 예측해 보자.

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 각 표적의 점수를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

선공이 가져갈 점수를 출력한다.

• $1 \leq N \leq 2 \times 10^5$
• $-10^9 \leq A_i \leq 10^9$