Cards
Maratona de Programação da SBC 
Brazil
Maratona de Programação da SBC Brazil
Two players, Alberto and Wanderley, play a game. A set with an even number of cards, each card containing an integer, is arranged on a table, one card next to another, forming a sequence of cards. Alberto begins to play, and can take one of two cards at the edges of the sequence (the first or the last card). Wanderley then can take one of two cards at the edges of the remaining sequence, and Alberto can again take a card from the sequence, and so on, until Wanderley takes the last card.
In this game, the number of points of a player is the sum of the numbers in the cards he took. Alberto, the first to play, aims to maximize his number of points. Wanderley, the second player, wants to make Alberto to have the least number of points possible. In short, both want to do their best, Alberto wanting to maximize his points and Wanderley wanting to minimize Alberto’s points.
You must write a program that, given the sequence of cards, determines the highest number of points that Alberto can get.
The input contains several test cases. Each test case is described in two lines. The first line contains an even integer N (2 ≤ N ≤ 104), which indicates the number of cards on the table. The second line contains N integers, describing the sequence of cards. Each of the N integers can fit in 32 bits.
For each test case your program must print a single line, containing a single integer, the largest number of points that Alberto can get.
| Sample Input | Sample Output |
|
4 |
10 |