#include<bits/stdc++.h>
using namespace std;

const int N=20010;
int n;
int dp[N][N];
int s[N]; //维护一维前缀和

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i];
	for(int i=1;i<=n;i++) s[i]+=s[i-1];
	
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i<=n;i++)
		{
			int l=i,r=i+len-1;
			dp[l][r]=1e6; //放的位置不能放在k循环内
			for(int k=l;k<=r-1;k++)
			{
				dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
			}
		}
	}
	
	cout<<dp[1][n];
	return 0;
}