Untitled

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;


int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    long N;
    cin>>N;

    long dp[N][N];
    long seq[N],sum[N+1];
    for(int i = 1 ; i <= N ; i++){
        cin>>seq[i];
        sum[i] = sum[i-1] + seq[i];
    }
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= N ; j++){
            dp[i][j] = 0;
        }
    }

    for(int len = 3 ; len <= N ; len ++){
        for(int l = 1 ; l+len-1 <= N ; l ++){
            long r = l+len-1;
            dp[l][r] = -INF;
            if(len != 1){
                for(int i = l ; i < r ; i++){
                    for(int j = r ; j > 0 ; j--){
                        dp[l][r] = max(dp[l][r],dp[l][i-1] + dp[i][j] + dp[j+1][r] + sum[i-1]*(sum[r]-sum[j]) -(sum[j] - sum[i-1]));
                        //cout<<dp[l][r]<<"\n";
                        //cout<<sum[i-1]<<" "<<sum[r]<<" "<<sum[j]<<"\n";
                    }
                }
            }

        }
    }
    cout<<dp[1][N];

    return 0;
}