쿠키 게임

Gustav와 Oskar는 기지에서 쿠키 몇 개를 발견하여, 탁자 위에 한 줄로 놓고 왼쪽에서 오른쪽으로 $1$부터 $n$까지 번호를 매겼다. 쿠키 번호 $i$을 먹는 데는 $a_i$번 베어 먹어야 한다. Gustav와 Oskar는 쿠키를 먹고 싶지만, 쿠키를 둘이 어떻게 나눌지 합의하지 못했기 때문에 게임을 하기로 했다. 두 사람은 번갈아 가며 행동한다. 한 번의 행동은 다음 중 하나이다.

• 탁자에서 쿠키 하나를 가져간다.

• 이전에 가져간 쿠키를 한입 베어 먹는다.

Gustav나 Oskar가 쿠키를 가져가면, 다른 쿠키를 가져가기 전에 그 쿠키를 다 먹어야 한다. 남은 쿠키가 없고 한 플레이어가 마지막 쿠키를 다 먹었다면, 다른 플레이어가 자신의 쿠키를 다 먹을 때까지 기다려야 한다.

Oskar는 새 쿠키를 가져갈 수 있을 때 항상 가장 왼쪽의 쿠키(인덱스가 가장 낮은 쿠키)를 가져가는 전략을 사용한다. Gustav가 먼저 행동하며 가능한 한 많은 쿠키를 먹고 싶어 한다. Oskar의 전략을 알고 최적으로 플레이한다면 쿠키를 몇 개 먹을 수 있는가?

채점

그룹 | 점수 | 제한 조건

$1$ |$25$| $n \leq 20, a_i \leq 20$

$2$ |$20$| $n \leq 75, a_i \leq 75$

$3$ |$15$| $n \leq 250, a_i \leq 10^9$

$4$ |$40$| $n \leq 5000, a_i \leq 10^9$

첫째 줄에 정수 $n$이 주어진다. 둘째 줄에는 공백으로 구분된 $n$개의 정수 $a_i$ ($1 \leq a_i$)가 주어진다.

Gustav가 얻을 수 있는 쿠키 수의 최댓값을 나타내는 정수 하나를 출력한다.