/*



























































































4
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 404
10 20 30 40





















//#include <bits/stdc++.h>
//using namespace std;
//string s[5][3055],s1,s2;
//int sol,dp[5][3055],ans,n,m,ma;
//int main()
//{
//
//    cin>>s1>>s2;
//    if (s1.size()>s2.size()) swap(s1,s2);
//    n=s1.size();
//    m=s2.size();
//    for (int i=0; i<n; i++)
//    {
//        for (int j=0; j<m; j++)
//        {
//            sol=0;
//            if (s1[i]==s2[j])
//            {
//                dp[1][j+1]=dp[0][j]+1;
//                sol=1;
//
//            }
//            if (dp[1][j+1]<dp[1][j])
//            {
//                dp[1][j+1]=dp[1][j];
//                sol=2;
//
//            }
//            if (dp[0][j+1]>dp[1][j+1])
//            {
//                dp[1][j+1]=dp[0][j+1];
//                sol=3;
//
//            }
//            if (sol==1)  s[1][j+1]=s[0][j]+s1[i];
//            if (sol==2)  s[1][j+1]=s[1][j];
//            if (sol==3)  s[1][j+1]=s[0][j+1];
//            if (i==n-1)
//            {
//                if (dp[1][j+1]>ma)
//                {
//                    ma=dp[1][j+1];
//                    ans=j+1;
//                }
//            }
//        }
//        for (int j=0;j<m;j++)
//        {
//            dp[0][j+1]=dp[1][j+1];
//            s[0][j+1]=s[1][j+1];
//        }
//
//    }
//    cout<<s[1][ans];
}*/
#include <bits/stdc++.h>
using namespace std;
long long n,a[455],dp[455][455],siz[455][455],sum[455];
int main()
{
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for (int i=0;i<n;i++)
    {
        cin>>a[i];
        dp[i][i]=0;
        siz[i][i]=a[i];
         sum[i+1]=a[i]+sum[i];
    }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n && j+i<n ;j++)
        {
            if (dp[j][j+i]==-1)  dp[j][j+i]=9999999999999999;
            for (int k=j;k<i+j;k++)
            {
                dp[j][i+j]=min(dp[j][i+j],dp[j][k]+dp[k+1][i+j]+siz[j][k]+siz[k+1][i+j]);
                siz[j][i+j]=sum[i+j+1]-sum[j];
            }
            //cout<<j<<"  "<<i+j<<"  "<<dp[j][j+i]<<endl;
            }
        }

    cout<<dp[0][n-1];
}


Measured memory_bytes: 3328