/**

  * uva

  * Problem#10891

  * Accepted

  * Time:0ms

  */

 #include<iostream>

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<sstream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 #include<stack>

 using namespace std;

 typedef bool boolean;

 #define INF 0xfffffff

 #define smin(a, b) a = min(a, b)

 #define smax(a, b) a = max(a, b)

 template<typename T>

 inline void readInteger(T& u){

     char x;

     long long aFlag = ;

     while(!isdigit((x = getchar())) && x != '-');

     if(x == '-'){

         x = getchar();

         aFlag = -;

     }

     for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');

     ungetc(x, stdin);

     u *= aFlag;

 }

 int n;

 int *list;

 int f[][];

 int g[][];

 int dp[][];

 inline boolean init(){

     readInteger(n);

     if(n == )    return false;

     list = new int[(const int)(n + )];

     for(int i = ; i <= n; i++){

         readInteger(list[i]);

     }

     return true;

 }

 int *sum;

 inline void getSum(){

     sum = new int[(const int)(n + )];

     sum[] = ;

     for(int i = ; i <= n; i++)

         sum[i] = sum[i - ] + list[i];

 }

 inline void solve(){

     memset(f, 0x7f, sizeof(f));

     memset(g, 0x7f, sizeof(g));

     for(int i = ; i <= n; i++)    f[i][i] = g[i][i] = dp[i][i] = list[i];

     for(int k = ; k < n; k++){

         for(int i = ; i + k <= n; i++){

             int j = i + k;

             int m = ;

             smin(m, f[i + ][j]);

             smin(m, g[i][j - ]);

             dp[i][j] = sum[j] - sum[i - ] - m;

             f[i][j] = min(f[i + ][j], dp[i][j]);

             g[i][j] = min(g[i][j - ], dp[i][j]);

         }

     }

     printf("%d\n", dp[][n] *  - sum[n]);

     delete[] list;

     delete[] sum;

 }

 int main(){

     while(init()){

         getSum();

         solve();

     }

     return ;

 }