#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N= 1010;

int n;
int s[N],f[N][N];
/*
在顺序固定的一排石堆上 每次合并相邻的石堆 求最小代价

化解子问题
最后合并成一堆时 肯定是由两堆合并而来
那就是要让这两堆的代价最小
用f[i][j]表示i~j这一些堆合并起来的最小代价
最终答案就是f[1][n]

用i~k表示左边石堆 k+1~j表示右边石堆
则i~j的最小代价是f[i][j] = min(f[i][k] + f[k+1][j] + sum[i][j])
其中sum[i][j]表示i~j这堆石堆之和 可以用前缀和优化
*/
int main()
{
    cin>>n;
    for(int i = 1; i<=n; i++)
    {
        cin>>s[i];
        s[i] += s[i-1];
    }
    //区间DP
    //先枚举区间长度
    //因为合并石堆至少需要两堆 所以区间长度从2开始
    for(int len = 2; len<=n; len++)
        for(int l = 1; l+len-1<=n; l++)//枚举左端点
        {
            int r = l+len-1;//确定右端点
            f[l][r] = 1e9;//初始化最大值
            for(int k = l; k<r; k++)//在区间上枚举
                f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
        cout<<f[1][n];
    return 0;
}