동전 게임

수진과 지훈은 동전을 가지고 재미있는 게임을 하기로 했습니다. 동전들은 각각 서로 다른 가치를 가지고 있으며, 이 동전들로 이루어진 라인을 앞에서부터 혹은 뒤에서부터 차례대로 하나씩 가져가며 게임을 합니다.

총 N (1 <= N <= 5,000) 개의 동전이 있고, 각 동전의 가치는 C_i (1 <= C_i <= 5,000)로 표시됩니다. 동전은 직선으로 놓여있습니다. 수진과 지훈은 번갈아가면서 동전을 가져갑니다. 자신의 차례가 되면, 한 번에 라인의 맨 앞이나 맨 뒤에 있는 동전 하나를 가져갈 수 있습니다. 동전이 모두 없어질 때까지 게임은 계속됩니다.

수진과 지훈는 각자 자신이 가져간 동전의 가치의 총합이 최대가 되도록 열심히 게임을 합니다. 수진이 먼저 게임을 시작합니다.

두 사람이 각자 최적의 전략으로 게임을 진행한다고 가정했을 때, 수진이 얻을 수 있는 동전 가치의 최대 총합을 얼마인지 계산해주세요. 

예를 들어, 다음과 같은 값이 있는 네 개의 동전이 일렬로 놓여 있는 게임을 생각해봅시다:

30  25  10  35

이 게임의 순서는 다음과 같습니다:

                             수진       지훈        New Coin
Player   Side   CoinValue   Total     Total         Line
 수진     Right     35        35         0        30  25  10
 지훈     Left      30        35        30          25  10
 수진     Left      25        60        30            10
 지훈     Right     10        60        40            --

이것이 수진이 할 수 있는 최선의 게임입니다.

• 1번째 줄: 하나의 정수: N
• 2번째 줄...N+1번째 줄 : i+1번째 줄에는 하나의 정수가 포함됩니다: C_i

• 1번째 줄: 수진이 최적의 전략으로 플레이를 할 때 총 수익이 되는 가장 큰 단일 정수.