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;

class Main {

    public static void playGame(long[] sequence) {
        long[][] dp = new long[sequence.length + 1][sequence.length + 1];

        for(int i=1; i<=sequence.length; i++)
            dp[i][i] = sequence[i-1];

        for(int gap= 1; gap<sequence.length; gap++) {

            for(int start = 1, end = start + gap; start <= sequence.length && end <= sequence.length ; start++, end++) {
                dp[start][end] = Math.max(sequence[start-1] - dp[start+1][end], sequence[end-1] - dp[start][end-1]);
            }

        }

        System.out.println(dp[1][sequence.length]);
    }


    public static void playGameMemo(long[] sequence) {
        long[][] memo = new long[sequence.length][sequence.length];
        for(int i=0; i<sequence.length; i++)
            Arrays.fill(memo[i], -1);
        long maxValueAttainable = playGameMemoHelper(sequence, memo, 0, sequence.length - 1);
        long sum = 0;

        for(int i=0; i<sequence.length; i++)
            sum = sum + sequence[i];
        long Y = sum - maxValueAttainable;
        System.out.println(maxValueAttainable - Y);
    }

    private static long playGameMemoHelper(long[] sequence, long[][] memo, int start, int end) {
        if(start > end) {
            return 0;
        }

        if(start == end) {
            return sequence[start];
        }

        if(start + 1 == end) {
            return memo[start][end] = Math.max(sequence[start], sequence[end]);
        }

        if(memo[start][end] != -1) {
            return memo[start][end];
        }

        long state1 = sequence[start] +  Math.min(playGameMemoHelper(sequence, memo, start+2, end), playGameMemoHelper(sequence, memo, start + 1, end - 1));
        long state2 = sequence[end] + Math.min(playGameMemoHelper(sequence, memo, start + 1, end - 1), playGameMemoHelper(sequence, memo, start, end - 2 ));

        return memo[start][end] = Math.max(state1, state2);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();

        long[] sequence = new long[N];

        for(int i=0; i<N; i++) {
            sequence[i] = scanner.nextLong();
        }

        //playGame(sequence);
        playGameMemo(sequence);
    }

}
