#include <bits/stdc++.h>
const int N = 1005;
long long f[N][N];
long long a[N],s[N];
int n;
using namespace std;
int main()
{
	freopen("shizi.in","r",stdin);
	freopen("shizi.out","w",stdout);
	cin >> n;
	memset(f,0x3f,sizeof(f));
	for(int i = 1;i <= n;i++)
	{
		f[i][i] = 0;
		cin >> a[i];
		s[i] = s[i-1] + a[i];
	}
	for(int len = 2;len <= n;len++)
	{
		for(int l = 1;l <= n - len + 1;l++)
		{
			int r = l + len - 1;
			for(int k = l;k < r;k++)
				f[l][r] = min(f[l][r],f[l][k] + f[k+1][r]);
			f[l][r] += s[r] - s[l-1];
		}
	}
	cout << f[1][n] << endl;
	return 0;
}