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.io.*;
import java.util.*;


public class Main {
    int INF = (int)1e9;
    long MOD = 1000000007;

    long max(long...x) {long rs = x[0]; for(long y: x) rs = Math.max(rs, y); return rs;}
    long min(long...x) {long rs = x[0]; for(long y: x) rs = Math.min(rs, y); return rs;}
    

    HashMap<Long, Long> mp;

    long go(long[] a, int n, int i, int j, int t) {
        if(i>j) {
            return 0;
        }
        if(i+1==j) {
            if(t==0) {
                return max(a[i]-a[j], a[j]-a[i]);
            }
            return min(a[i]-a[j], a[j]-a[i]);
        }
        long k = 10000000*i + j*10 + t;
        if(mp.containsKey(k)) return mp.get(k);

        long x = go(a, n, i+1, j, t^1) + (t==0?a[i]:-a[i]);
        long y = go(a, n, i, j-1, t^1) + (t==0?a[j]:-a[j]);
        
        long rs = max(x, y);
        if(t==1) rs = min(x, y);
        mp.put(k, rs);
        return rs;
    }

    void solve(InputReader in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        long[] a = new long[n];
        for(int i=0; i<n; i++) {
            a[i] = in.nextInt();
        }
        // mp = new HashMap<Long, Long>();
        // long rs = go(a, n, 0, n-1, 0);
        // out.println(rs);
        long[][] dp = new long[n][n];
        for(int i=n-1; i>=0; i--) {
            for(int j=i; j<n; j++) {
                if(i==j) {
                    dp[i][j] = a[i];
                    // dp[i][j][1] = -a[i];
                } else {
                    dp[i][j] = max(-dp[i][j-1] + a[j], -dp[i+1][j] + a[i]);
                    // dp[i][j][1] = min(dp[i][j-1][0] - a[j], dp[i+1][j][0] - a[i]);
                }
            }
        }
        out.println(dp[0][n-1]);
    }
    

    public static void main(String[] args) throws IOException {
        if(args.length>0 && args[0].equalsIgnoreCase("d")) {
            DEBUG_FLAG = true;
        }
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int t = 1;//in.nextInt();
        long start = System.nanoTime();
        while(t-- >0) {
            new Main().solve(in, out);
        }
        long end = System.nanoTime();
        debug("\nTime: " + (end-start)/1e6 + " \n\n");
        out.close();
    }
    
    static boolean DEBUG_FLAG = false;
    static void debug(String s) {
        if(DEBUG_FLAG) System.out.print(s);
    }
    
    public static void show(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    
    static class InputReader {
        static BufferedReader br;
        static StringTokenizer st;
    
        public InputReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        
        long nextLong() {
            return Long.parseLong(next());
        }
        
        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}