#描述#
Bessie and Bonnie have found a treasure chest full of marvelous
gold coins! Being cows, though, they can't just walk into a store and
buy stuff, so instead they decide to have some fun with the coins.
<BR>
<BR>
The N (1 <= N <= 5,000) coins, each with some value C_i (1 <= C_i
<= 5,000) are placed in a straight line. Bessie and Bonnie take turns,
and for each cow's turn, she takes exactly one coin off of either
the left end or the right end of the line. The game ends when there
are no coins left.
<BR>
<BR>
Bessie and Bonnie are each trying to get as much wealth as possible for
themselves. Bessie goes first. Help her figure out the maximum
value she can win, assuming that both cows play optimally.
<BR>
<BR>
Consider a game in which four coins are lined up with these values:
<BR>
30 25 10 35
<BR>
Consider this game sequence:
<BR>

<BR>
Player Side CoinValue BessieTotal BonnieTotal NewCoinLine
<BR>
Bessie Right 35 35 0 30 25 10
<BR>
Bonnie Left 30 35 30 25 10
<BR>
Bessie Left 25 60 30 10
<BR>
Bonnie Right 10 60 40 --
<BR>
This is the best game Bessie can play.

#格式#
##输入格式##
（多组数据）
* Line 1: A single integer: N

• Lines 2..N+1: Line i+1 contains a single integer: C_i

##输出格式##
* Line 1: A single integer, which is the greatest total value Bessie
can win if both cows play optimally.

#样例1#
##样例输入1##

4
30
25
10
35

##样例输出1##

60

#限制#
1000ms
32768KB

#提示#

#来源#