Taro and Jiro will play the following game against each other.

Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N). Until a becomes empty, the two players perform the following operation alternately, starting from Taro:

* Remove the element at the beginning or the end of a. The player earns x points, where x is the removed element.



Let X and Y be Taro's and Jiro's total score at the end of the game, respectively. Taro tries to maximize X - Y, while Jiro tries to minimize X - Y.

Assuming that the two players play optimally, find the resulting value of X - Y.

Constraints

* All values in input are integers.
* 1 \leq N \leq 3000
* 1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
a_1 a_2 \ldots a_N


Output

Print the resulting value of X - Y, assuming that the two players play optimally.

Examples

Input

4
10 80 90 30


Output

10


Input

3
10 100 10


Output

-80


Input

1
10


Output

10


Input

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1


Output

4999999995


Input

6
4 2 9 7 1 5


Output

2
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final Scanner sc    = new Scanner(System.in);
    static final int     MOD   = (int) 1E9 + 7;
    static final long    INF_L = (long) 4E18;

    public static void main(String[] args) {
        int N = nint();
        int[] a = nints(N, 1, 0);
        
        long[][] dp = new long[N+1][N+1];
        for (int n = 1; n <= N; n++) {
            if (taroMoves(N, n, n)) {
                dp[n][n] = a[n];
            } else {
                dp[n][n] = -a[n];
            }
        }
        
        for (int diff = 1; diff < N; diff++) {
            for (int l = 1; l + diff <= N; l++) {
                int r = l + diff;
                
                if (taroMoves(N, l, r)) {
                    dp[l][r] = max(dp[l+1][r  ] + a[l],
                                   dp[l  ][r-1] + a[r]);
                } else {
                    dp[l][r] = min(dp[l+1][r  ] - a[l],
                                   dp[l  ][r-1] - a[r]);
                }
            }
        }
        
        System.out.println(dp[1][N]);
    }
    
    static boolean taroMoves(int N, int l, int r) {
        return (N - (r - l) + 1) % 2 == 0;
    }

    @Deprecated
    static int nint() {
        return sc.nextInt();
    }

    @Deprecated
    static int[] nints(int N) {
        return nints(N, 0, 0);
    }

    @Deprecated
    private static int[] nints(int N, int padL, int padR) {
        int[] a = new int[padL + N + padR];
        for (int i = 0; i < N; i++)
            a[padL + i] = nint();
        return a;
    }

    static long nlong() {
        return sc.nextLong();
    }

    static long[] nlongs(int N) {
        return nlongs(N, 0, 0);
    }

    static long[] nlongs(int N, int padL, int padR) {
        long[] a = new long[padL + N + padR];
        for (int i = 0; i < N; i++)
            a[padL + i] = nlong();
        return a;
    }

    static double ndouble() {
        return sc.nextDouble();
    }

    static double[] ndoubles(int N) {
        return ndoubles(N, 0, 0);
    }

    static double[] ndoubles(int N, int padL, int padR) {
        double[] d = new double[N + padL + padR];
        for (int i = 0; i < N; i++) {
            d[padL + i] = ndouble();
        }
        return d;
    }

    static String nstr() {
        return sc.next();
    }

    static char[] nchars() {
        return sc.next().toCharArray();
    }

    static char[] nchars(int padL, int padR) {
        char[] temp = sc.next().toCharArray();
        char[] ret = new char[temp.length + padL + padR];
        System.arraycopy(temp, 0, ret, padL, temp.length);
        return ret;
    }

    static char[][] nchars2(int H, int W) {
        return nchars2(H, W, 0, 0);
    }

    static char[][] nchars2(int H, int W, int padLU, int padRD) {
        char[][] a2 = new char[H + padLU + padRD][W + padLU + padRD];
        for (int i = 0; i < H; i++)
            System.arraycopy(nchars(), 0, a2[padLU + i], padLU, W);
        return a2;
    }

    static long min(long... ls) {
        return Arrays.stream(ls).min().getAsLong();
    }

    static long max(long... ls) {
        return Arrays.stream(ls).max().getAsLong();
    }

    static long abs(long a) {
        return Math.abs(a);
    }
}
