/**
 * Let A(i, j) be player 1's score in the game when the front of the deque is
 * at index i in the array and the back of the deque is at index j in the
 * array, assuming optimal play from both players.  Likewise, let B(i, j) be
 * player 2's score in the game in this state.  We note that player 1 plays
 * to maximize X - Y, while player 2 plays to minimize X - Y.
 *
 * Because there's a finite total number of points available - i.e., for any
 * game involving the same sequence, X + Y = sum(a), where sum(a) is constant,
 * maximizing X - Y for player 1 is equivalent to maximizing X - (c - X) = 2X -
 * sum(a).  This expression is clearly maximized if and only if X is maximized.
 * A similar argument also holds for minimization, in that X - Y will be
 * minimized and only if X is minimized.
 *
 * On player 1's move, they have two options - they can take the left element
 * from the deque, or they can take the right element from the deque.  Once
 * they've taken it, player 2 will take either the left or right element.
 *
 * Let's suppose it's player 1's turn.  They can pick either the left or the
 * right element.  Once they do, player 2 has two options, and it can be
 * assumed that they will pick the one which minimizes player 1's possible
 * score.  Thus, for instance, if player 1 picks the left element, they can
 * expect their score to be a(i) plus the worst case based on player 2's two
 * possible choices:
 *
 * A(i, j) = a(i) + min(A(i+1, j-1), A(i+2, j)).
 *
 * Likewise, if player 2 picks the right element, they can expect their score
 * to be:
 *
 * A(i, j) = a(j) + min(A(i+1, j-1), A(i, j-2)).
 *
 * And thus, the optimal A(i, j) is simply:
 *
 * A(i, j) = max(a(i) + min(A(i+1, j-1), A(i+2, j)), a(j) + min(A(i+1, j-1), A(i, j-2)))
 *
 * And the value of X - Y when we've built the array is simply:
 *
 * 2A(0, n-1) - sum(a).
 *
 * Stated more plainly, we have that:
 *
 * A(i, j) = max(a(i) + min(A(i+1, j-1), A(i+2, j)), a(j) + min(A(i+1, j-1), A(i, j-2))) for i <= j.
 * A(i, j) = 0 for i > j or i > n-1 or j < 0.
 *
 * We can further simplify, assuming all of our i and j values are in the range [0, n-1]:
 *
 * A(i, j) = max(a(i) + min(A(i+1, j-1), A(i+2, j)), a(j) + min(A(i+1, j-1), A(i, j-2))) for j - i >= 2.
 * A(i, j) = max(a(i), a(j)) for 0 <= j - i <= 1.
 * A(i, j) = 0 for j - i < 0.
 */

#include <stdio.h>
#include <stdlib.h>

long max(long a, long b)
{
    return a > b ? a : b;
}

long min(long a, long b)
{
	return a < b ? a : b;
}

long sum(int *a, int n)
{
	int i;
	long sum = 0;
	
	for (i=0; i<n; i++)
	{
		sum += a[i];
	}
	
	return sum;
}

long solution(int *a, int n)
{
	long A[n][n];
	int i, j;
	
	for (i=0; i<n; i++)
	{
		for (j=0; j<n; j++)
		{
			if (i > j)
			{
				A[i][j] = 0;
			}
			else if (i + 2 > j)
			{
				A[i][j] = max(a[i], a[j]);
			}
		}
	}
	
	for (i=n-3; i>=0; i--)
	{
		for (j=i+2; j<n; j++)
		{
			A[i][j] = max(a[i] + min(A[i+1][j-1], A[i+2][j]), a[j] + min(A[i+1][j-1], A[i][j-2]));
		}
	}
	
	/*for (i=0; i<n; i++)
	{
		for (j=0; j<n; j++)
		{
			printf("%ld\t", A[i][j]);
		}
		printf("\n");
	}*/
	
	return 2*A[0][n-1] - sum(a, n);
}

int main(void)
{
    int n;
    int i;
    
    scanf("%d", &n);
    
    int a[n];
    
    for (i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    
    printf("%ld", solution(a, n));
    
	return 0;
}

Measured memory_bytes: 70528