The sheet of paper contains n (2 ≤ n ≤ 100, n is even) positive integers. Each number does not exceed 200. Two players are playing. For each move, you can cross out either leftmost or rightmost number. The crossed out number is added to the player's points.

Print the maximum possible amount of points for the first player, provided that the opponent plays the best possible way.

Input

First line contains one integer n (2 ≤ n ≤ 100, n четное). Next n lines contain the list of integers, one number in a line.

Output

Print the maximum possible amount of points for the first player if the second player plays the best.