초콜릿 게임

아지즈칸과 테미룰란은 스위스 초콜릿을 좋아한다. 최근 두 사람은 한 줄로 늘어선 $n$개 조각짜리 초콜릿 바를 샀다. 각 조각에는 단맛이 정해져 있으며, 단맛은 음수일 수도 있다. 조각은 왼쪽에서 오른쪽으로 $1, 2, \ldots, n$번 번호가 매겨져 있다. 아지즈칸은 왼쪽에서, 테미룰란은 오른쪽에서 번갈아 먹는다. 각 차례에 한 조각 이상을 먹어야 한다. 아지즈칸이 먼저 먹으며, 첫 차례에는 1개 또는 2개를 먹을 수 있다. 직전 차례에 $k$개를 먹었다면, 현재 차례의 사람은 $k$개 또는 $k + 1$개를 먹어야 한다. 다음 차례를 진행할 수 없으면 먹기를 멈춘다. 두 사람은 모두 상대보다 많은 단맛을 먹으려 하며, 자신이 먹은 조각의 단맛 합에서 상대가 먹은 조각의 단맛 합을 뺀 값을 최대화하려 한다. 두 사람이 모두 최적으로 행동할 때, 아지즈칸이 먹은 단맛 합과 테미룰란이 먹은 단맛 합의 차이를 구하라.

첫째 줄에 조각의 개수를 나타내는 정수 $n$ ($1 \le n \le 4000$)이 주어진다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($-10^4 \le a_i \le 10^4$)이 주어진다. 각 값은 해당 조각의 단맛이다.

두 사람이 모두 최적으로 행동할 때, 아지즈칸이 먹은 단맛 합에서 테미룰란이 먹은 단맛 합을 뺀 값을 한 줄에 출력한다.