slimes

//#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>

#define long long long
#define nln '\n'

const long N = 410, I = 1e18;

using namespace std;

// Global variables: n, a

long n;
vector<long> a;

void data()
{
    cin >> n;
    a.resize(n+1, 0);
    for (long i = 1; i <= n; ++i)
        cin >> a[i];
}

vector<long> sum;

long total(long i, long j)
{
    return sum[j] - sum[i-1];
}

void process()
{
    sum.resize(n+1, 0);
    for (long i = 1; i <= n; ++i)
        sum[i] = sum[i-1] + a[i];
    // Dynamic planning
    long dp[N][N];

    for (long i = 1; i <= n; ++i) dp[i][i + 1] = a[i] + a[i + 1];

    for (long i = 2; i <= n; ++i)
        for (long j = 1; j+i <=n; ++j)
        {
            long lef = j, rig = j+i;
            dp[lef][rig] = I;
            for (long k = lef+1; k <= rig; ++k)
                dp[lef][rig] = min(dp[lef][rig], dp[lef][k-1]+dp[k][rig]);
            dp[lef][rig] += total(lef, rig);
        }
    cout << dp[1][n] << nln;
}

int main()
{
    data();
    process();
    return 0;
}