#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#include<string>using namespace std;typedef  long long   ll;#define  rep(i,a,b)  for(int i=a; i<=b; ++i)#define  inf  1e18const int N=1005;int n, a[N];ll  dp[N][N], f[N][N], sum[N][N], sum1[N];int main(){    while(scanf("%d", &n)!=EOF)     {        rep(i,1,N-1) rep(j,i,N-1) dp[i][j]=inf;        rep(i,1,n)  scanf("%d", &a[i]), sum1[i]=sum1[i-1]+a[i];        rep(i,1,n) rep(j,i+1,n) {            sum[i][j]=sum1[j]-sum1[i-1];        }        rep(i,1,n) f[i][i]=i, dp[i][i]=0;        rep(len, 2, n)              for(int i=1; i+len-1<=n; ++i)        {            int j=i+len-1;            for(int k=f[i][j-1]; k<=f[i+1][j]; ++k)            {                    if(dp[i][j]>dp[i][k]+dp[k+1][j]+sum[i][j]) {                    dp[i][j]= dp[i][k]+dp[k+1][j]+sum[i][j];                    f[i][j]=k;                }            }            }        printf("%lld\n", dp[1][n]);    }            return 0;}