A-point

#include<stdio.h>
typedef long long int ll;
ll data[610];
ll qs[610];
ll dp[610][610];
ll max(ll a,ll b){
    return (a > b ? a : b);
}
ll min(ll a,ll b){
    return (a < b ? a : b);
}

ll cal(int l,int r){
    if(l == r)return 0;
    if(r - l == 1){
        return min(data[l],data[r])*2 + max(data[l],data[r]);
    }
    if(dp[l][r] == -2e9)dp[l][r] = max((2*data[l]) + (qs[r] - qs[l]) + cal(l+1,r) , (2*data[r]) + (qs[r-1] - qs[l-1]) + cal(l,r-1));
    return dp[l][r];
}


int main()
{
    for(int i=0;i<610;i++)for(int j=0;j<610;j++)dp[i][j] = -2e9;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&data[i]);
        qs[i] = qs[i-1] + data[i];
    }
    printf("%lld",cal(1,n));
    return 0;
}