List Game

You are given a list consisting of ~N~ natural numbers. Two players play the following game by repeating, first one and then the other, the following move: they select one of the numbers at the ends of the list (left or right), remove it from the list, and add it to their score. The game ends when all the numbers in the list are exhausted. Each player tries to maximize their final score.

Find the maximum score the first player can have at the end of the game, assuming both players play optimally.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the data and finds the maximum possible score of the first player if both of them play optimally.

Input Files:

The input file named listgame.in is a text file with exactly two lines. The first line contains an integer ~N~, the number of numbers in the list. The second line contains exactly ~N~ integers, separated in pairs by a single space: the ~N~ numbers of the list.

Output Files:

The output file named listgame.out is a text file consisting of a single line containing an integer: the maximum possible score of the first player if both of them play optimally.

Examples of Input - Output Files:

1st

STDIN (listgame.in)

10
6 3 9 2 10 4 9 2 3 7

STDOUT (listgame.out)

38

Explanation: The two players can choose to make the following moves, in order. These moves are optimal for both players.

2nd

STDIN (listgame.in)

5
10 2 1 4 3

STDOUT (listgame.out)

14

3d

STDIN (listgame.in)

6
4 8 0 1 5 6

STDOUT (listgame.out)

15

Constraints:

• The sum of all numbers on the list will not exceed ~10^9~.
• For test cases worth 25%, of the total points, it will be: 1 ~\le~ Ν ~\le~ 20

• For test cases worth 100%, of the total points, it will be: 1 ~\le~ Ν ~\le~ 10.000

• Formatting: In both the input and the output, each line terminates with a newline character.
  

• Maximum execution time: 1 sec.
  
• Maximum available memory: 64 MB.
  
• Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: listgame *)

for PASCAL coders

/* USER: username
LANG: C
TASK: listgame */

for C coders

/* USER: username
LANG: C++
TASK: listgame */

for C++ coders

/* USER: username
LANG: Java
TASK: listgame */

for Java coders

# USER: username
# LANG: Python
# TASK: listgame

for Python coders