// Original C++ solution (slower):
/*

                " اللهم صلي و سلم علي سيدنا محمد و علي اله وصحبه اجمعين "

*/



#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

#define f for

#define ll long long

#define ull unsigned long long

#define endl "\n"

#define intial(s1, s2, x, dp) f(int i = 0; i < s1; i++) f(int j = 0; j < s2; j++) dp[i][j] = x;

using namespace std;

#define BI acos(-1)

#define all(a) a.begin(), a.end()

#define loop1(n) f(int i = 0; i < n; i++)

#define loop2(n) f(int j = 0; j < n; j++)

#define oo 1e9;

void Open()

{

    freopen("Input.txt", "r", stdin);

    freopen("Output.txt", "w", stdout);

}

ll gcd(ll a, ll b)

{

    return b == 0 ? a : gcd(b, a % b);

}

void madesetprobblem()

{

    //$ $

    //less than or equal => $ 1 \leq 100 $

    //  $(1 \le A,B \le 10^5 )$

    // a[i] => $a_i$

    // a[i][j] => $a_{i,j}$

    // double qoutes ''yext''

    /*

        image

        \begine{center}

        \includegraphics{image.jpg}

        \end{center}

    */

    /*

        list

        \begin{itemize}

            \item first one

            \item second one

        \end{itemize}

    */

}

ll n,*a,*b;

ll dp[401][401];

ll ans(int i,int j)

{

    ll& ret=dp[i][j];

    if(~ret)return ret;

    if(j-i==0)

    {

        return ret=0;

    }

    if(j-i==1)

    {

        return ret=a[i]+a[j];

    }

    if(j-i==2)

    {

        return ret=min(a[i]+2*a[i+1]+2*a[i+2],2*a[i]+2*a[i+1]+a[i+2]);

    }

    ret=1e14;

    f(int c=i;c<=j;c++)

    {

        ll x=(ans(i,c)+(b[c+1]-b[i]))+(ans(c+1,j)+(b[j+1]-b[c+1]));

      //  cout<<x<<' '<<i<<' '<<j<<endl;

        ret=min(ret,x);

    }

    return ret;

}

int main()

{

    //Open();

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    memset(dp,-1,sizeof dp);

    cin>>n;

    a=new ll[n];

    b=new ll[n+1];

    memset(b,0,sizeof b);

    loop1(n)

    {

        cin>>a[i];

        b[i+1]=a[i]+b[i];

    }

    if(n==1)

    {

        cout<<a[0];

        return 0;

    }

    cout<<ans(0,n-1);

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define f first

#define s second

#define fore(i,a,b) for(int i = (a), ThxMK = (b); i < ThxMK; ++i)

#define pb push_back

#define all(s) begin(s), end(s)

#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define sz(s) int(s.size())

#define ENDL '\n'

using namespace std;

typedef long double ld;

typedef long long lli;

typedef pair<lli,lli> ii;

typedef vector<int> vi;

typedef vector<lli> vl;

typedef vector<ii> vii;

typedef vector<vi> vvi;

typedef vector<vl> vvl;

#define deb(x) cout << #x": " << (x) << endl;



const int N = 3e3+5;

const lli INF = 1e18;

const lli MOD = 1e9+7;



vi m;

vi primes(1,2);

vector<vector<ld>>nk;

void sieve(){

	m = vi(N+1,0);

	for(int i = 4; i<N; i+=2)m[i]=1;

	for(int i = 3; i*i<=N; i+=2)if(!m[i])for(int j = i*i; j<N; j+=i)m[j]=1;

	for(int i = 3; i<N; i+=2)if(!m[i])primes.pb(i);

}



void pascal(){

	nk =vector<vector<ld>>(N,vector<ld>(N,0.0));

	fore(i,0,N)nk[i][0]=nk[i][i]=1.0;

	fore(i,1,N)fore(j,1,i)nk[i][j]=nk[i-1][j-1]+nk[i-1][j];

}



lli gcd(lli a, lli b){return (b?gcd(b,a%b):a);}



lli lcm(lli a, lli b){

	if(a<b)swap(a,b);

	lli c = gcd(a,b);

	a/=c;

	return a*b;

}



int popcount(lli x) { return __builtin_popcountll(x); }



lli poww(lli a, lli b){

	lli res =1;

	while(b){

		if(b&1) res = res * a;

		a = a*a;

		b/=2;

	}

	return res;

}



lli powm(lli a, lli b){

	lli res =1;

	while(b){

		if(b&1) res = (res * a)%MOD;

		a = (a*a)%MOD;

		b/=2;

	}

	return res;

}



bool isPrime(lli x){

	if(x==1)return 0;

	for(auto i:primes){

		if(i*i>x)return 1;

		if(x%i==0)return 0;

	}

	return 1;

}



lli SUM(lli a, lli b, lli mod=MOD){

	return (a+b+mod)%mod;

}



int dx[4]={-1,0,0,1}, dy[4]={0,1,-1,0};



// ---- コーディングはここから！ ('-')7



void solve(){

	int n; cin>>n;

	vl v(n+1,0); fore(i,0,n)cin>>v[i];

	vvl dp(n,vl(n,-1));

	vl sum(n+1);

	sum[0]=v[0];

	fore(i,1,n+1)sum[i]=sum[i-1]+v[i];

	auto f=[&](auto f, int l, int r)->lli{

		if(l==r)return 0;

		if(dp[l][r]!=-1)return dp[l][r];

		dp[l][r]=INF;

		fore(i,l,r)dp[l][r]=min(dp[l][r],f(f,l,i)+f(f,i+1,r)+sum[r]-(l?sum[l-1]:0));

		return dp[l][r];

	};

	cout<<f(f,0,n-1)<<ENDL;

}



int main(){_

	//int t; cin>>t; while(t--)

	solve();

}


// Fastest known solution for this problem: