URI Online Judge | 1545

Cards II

By Gabriel Ilharco Magalhaes, ITA BR Brazil

Timelimit: 6

Wanderley, after discovering that Alberto cheated the previous game with the help of a computer, decided to stop playing with Alberto. Now, Alberto spends his afternoons playing by himself a one-player version of the card game they used to play, as follows. 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. In each round, Alberto takes one of two cards at the edges of the sequence (the first or the last card), which value is computed in his points. Alberto then takes one of two cards at the edges of the remaining sequence, and so on, until there are no remaining cards on the table.

In this game, the number of points of a player is the sum of the numbers in the cards he took (the cards he discarded does not count). Alberto aims to maximize his number of points. You must write a program that, given the sequence of cards, determines the highest number of points that Alberto can get.

Input

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 Nintegers, describing the sequence of cards. Each of the N integers can fit in 32 bits.

Output

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
0 -3 5 10
4
0 -3 5 7
4
47 50 -3 7

15
12
97