/* 
    @author : srinathbalaji_99
*/

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/assoc_container.hpp> 

using namespace std;
using namespace __gnu_pbds;

//------------------------MACROS START HERE----------------------------------//

#define     ordered_set_PLL         tree <PLL, null_type,less<PLL>, rb_tree_tag,tree_order_statistics_node_update>
#define     ordered_set             tree <LL, null_type,less<LL>, rb_tree_tag,tree_order_statistics_node_update>

//query 1 order_of_key (k)  : Number of items strictly less than k.
//query 2 find_by_order(k)  : k-th element in the set (counting from zero).
//less<ll>                  : query 1 will return numbers strictly less than k
//greater<ll>               : query 1 will return numbers strictly greater than k

#define     PB                      push_back
#define     MP                      make_pair
#define     endl                    '\n'
#define     MAX                     LLONG_MAX
#define     MIN                     LLONG_MIN
#define     rep(i, a, b, inc)       for(long long i = a; i < b; i += inc)
#define     REP(i, n)               rep(i, 0, n, 1)
#define     MEM(a, b)               memset(a, (b), sizeof(a))
#define     PI                      3.1415926535897932384626433832795
#define     MOD                     1000000007
#define     PLL                     pair<long long, long long>
#define     VL                      vector<long long>
#define     VS                      vector<string>
#define     VLL                     vector<PLL>
#define     VVL                     vector<VL>
#define     MPLL                    map<long long, long long>
#define     UMPLL                   unordered_map<long long, long long>
#define     SETL                    set<long long>
#define     MSETL                   multiset<long long>
#define     GCD(a, b)               __gcd(a, b)
#define     LCM(a, b)               (a * b)/GCD(a, b)
#define     ff                      first
#define     ss                      second
#define     pall(a)                 REP(i, sizeof(a)/sizeof(a[0]))cout << a[i] << " ";cout << endl;
#define     pvall(v)                REP(i, v.size())cout << v[i] << " ";cout << endl;
#define     pset(s)                 for(auto thing : s)cout << thing << " ";cout << endl;
#define     pmap(m)                 for(auto thing : m)cout << thing.ff << " " << thing.ss << endl;
#define     pvpair(v)               pmap(v)
#define     gall(a, n)              REP(i, n)cin >> a[i];
#define     all(x)                  x.begin(), x.end()
#define     rall(x)                 x.rbegin(), x.rend()

typedef unsigned long long ULL;
typedef long long LL;
typedef long double LD;

//------------------------MACROS END HERE-------------------------------------//

//------------------------tmpl8 FUNCTIONS START HERE--------------------------//

void    fast            ()                                          {ios_base::sync_with_stdio(false);cin.tie(NULL);}
VL      sieve           (LL n)                                      {vector<bool> is_prime(n + 1, true);is_prime[0] = false;is_prime[1] = false;VL primes;for(LL i = 2; i * i <= n; ++i){if(is_prime[i]){for(LL j = 2 * i; j <= n; j += i){is_prime[j] = false;}}}REP(i, is_prime.size()){if(is_prime[i]){primes.PB(i);}}return primes;}
LL      power_mod       (LL x, LL y, LL m)                          {LL res = 1;while(y > 0){if(y & 1){res = (res * x) % m;}y >>= 1;x = (x * x) % m;}return res;}
LL      mod_inverse     (LL x, LL m)                                {return power_mod(x, m - 2, m);}
LD      dist2d          (LL x1, LL y1, LL x2, LL y2)                {return sqrt((LD)((x1 - x2) * (x1 - x2)) + (LD)((y1 - y2) * (y1 - y2)));}
LD      dist3d          (LL x1, LL y1, LL z1, LL x2, LL y2, LL z2)  {return sqrt((LD)((x1 - x2) * (x1 - x2)) + (LD)((y1 - y2) * (y1 - y2)) + (LD)((z1 - z2) * (z1 - z2)));}
LD      slope           (LL x1, LL y1, LL x2, LL y2)                {return (LD)(y2 - y1) / (LD)(x2 - x1);}
LL      dot_product     (VL a, VL b)                                {LL sum = 0;REP(i, a.size()){sum += a[i] * b[i];}return sum;}

//------------------------tmpl8 FUNCTIONS END HERE------------------------------//

//---------------------------------custom---------------------------------------//
VL prefs;
LL sum(LL x, LL y){
    LL res = prefs[y];
    if(x > 0){
        res -= prefs[x - 1];
    }
    return res;
}

//---------------------------------custom---------------------------------------//

//------------------------PROGRAM STARTS HERE----------------------------------//

using namespace std;

int main()
{
    fast();


    LL t, n, m, k, x, y;
    cin >> n;
    LL a[n];
    gall(a, n);
    prefs.resize(n);
    prefs[0] = a[0];
    rep(i, 1, n, 1){
        prefs[i] = a[i] + prefs[i - 1];
    }
    LL dp[n][n];
    /*dp[i][j] -> denotes best way to combine i..j
    answer is dp[0][n - 1]*/
    REP(i, n){
        REP(j, n){
            dp[i][j] = MAX;
        }
    }
    REP(i, n){
        dp[i][i] = 0;
        if(i < n - 1){
            dp[i][i + 1] = a[i] + a[i + 1];
        }
    }
    for(LL len = 3; len <= n; ++len){
        REP(i, n - len + 1){
            for(LL j = i; j < i + len - 1; ++j){
                dp[i][i + len - 1] = min(dp[i][i + len - 1], dp[i][j] + sum(i, j) + dp[j + 1][i + len - 1] + sum(j + 1, i + len - 1));
            }
        }
    }
   
    cout << dp[0][n - 1] << endl;
    
}

//------------------------PROGRAM ENDS HERE----------------------------------//

Measured memory_bytes: 1536