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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author cplayer
 */
public class Main {
    public static void main (String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        LDeque solver = new LDeque();
        solver.solve(1, in, out);
        out.close();
    }

    static class LDeque {
        public void solve (int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            long[] a = in.nextLongArr(n + 1, 1, n);
            long[][] dp = new long[n + 1][n + 1];
            dp[0] = Arrays.copyOfRange(a, 0, n + 1);
            // 注意考虑的时候需要把对应的子区间值也考虑进去
            // 本题也可以有这样的写法：
            // if (len > 1) {
            //     dp[i][j] = Math.max(-dp[i + 1][j] + a[i], -dp[i][j - 1] + a[j]);
            // } else {
            //     dp[i][j] = a[i];
            // }
            // 这样就避免了过多的转移内容
            for (int i = 1; i <= n - 1; ++i) {
                for (int j = 1; j + i <= n; ++j) {
                    if (i > 1) {
                        long valFirstFirst = dp[i - 2][j + 2] + a[j] - a[j + 1], valFirstLast = dp[i - 2][j + 1] + a[j] - a[j + i];
                        long valLastFirst = dp[i - 2][j + 1] + a[j + i] - a[j], valLastLast = dp[i - 2][j] + a[j + i] - a[j + i - 1];
                        long valFirst = Math.min(valFirstFirst, valFirstLast);
                        long valLast = Math.min(valLastFirst, valLastLast);
                        dp[i][j] = valFirst > valLast ? valFirst : valLast;
                    } else if (i == 1) {
                        dp[i][j] = Math.max(a[j] - a[j + i], a[j + i] - a[j]);
                    }
                }
            }
            out.println(dp[n - 1][1]);
        }

    }

    static class InputReader {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        public InputReader (InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next () {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return tokenizer.nextToken();
        }

        public long[] nextLongArr (int length, int readOffset, int readLength) {
            long[] res = new long[length];
            for (int i = readOffset; i < readOffset + readLength; ++i) {
                res[i] = nextLong();
            }
            return res;
        }

        public int nextInt () {
            return Integer.parseInt(next());
        }

        public long nextLong () {
            return Long.parseLong(next());
        }

    }
}

