#include "iostream"
#include "fstream"
#include "algorithm"
#include "iomanip"
#include "stack"
#include "queue"
#include "string"
#include "vector"
#include "map"
#include "set"
#include "list"
#include "deque"
#include "complex"
#include "bitset"
#include "cmath"
#include "unordered_set"
#include "unordered_map"
#include "iterator"
#include <ctime>
#include <cassert>
#include "numeric"
#include <cstdio>

using namespace std;

//#define f(i,n) for(int i=0; i<n;i++) 
//#define rf(i, n) for(int i=n-1;i>=0;i--)
//#define forn(i, j, n) for(int i=j; i<n; i++)
//#define ff(i, j, n) f(i, n)f(j, n)
#define pb push_back
#define maxi(a,b) a = max(a, b);
#define mini(a,b) a = min(a, b);
#define endl '\n'
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sqr(x) ((x) * (x))
#define SZ(a) ((int)(a.size()))
#define watch(x) cout << (#x) << " = " << x << endl;
//typedef long long ll;
typedef long double ld;
#define int long long
#define double ld
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<pii> vpii;
typedef vector<char> vc;

template<class T>
void show(const vector<T> &a)
{
	for (T x : a)
		cout << x << " ";
	cout << endl;
}

const int sze = 3e5 + 50, oo = 1e18 + 500, mod1 = 1e9 + 7, mod = 998244353;
const double eps = 1e-9, PI = 2 * acos(0.0);
vi vertices[sze];
vi visit(sze, 0);
vc used(sze, false);
vi arr(sze, 0);
int n, m, k;
int A, B;
int cnt = 0;

//int dp[10010][110];
//int dpe[10010][10][110];

int dp[410][410];
bool did_dp[410][410];

vi pref(450, 0);
vi a(450);

int rec(int l, int r)
{
	if (l >= r)
		return 0;

	if (did_dp[l][r])
		return dp[l][r];

	did_dp[l][r] = true; 

	for (int i = l; i <= r-1; i++)
	{
		mini(dp[l][r], rec(l, i) + rec(i + 1, r) + pref[r] - pref[l - 1]);
	}
	
	return dp[l][r];
}

signed main() 
{
	ios::sync_with_stdio(0);
	cout.tie(0); cin.tie(0);

	/*string s;
	cin >> s >> m;
	n = SZ(s);

	for (int i = 1; i <= 9; i++)
	{
		dp[1][i % m] ++;
	}

	for (int i = 2; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			for (int z = 0; z <= 9; z++)
			{
				dp[i][(j + z) % m] = (dp[i - 1][j] + dp[i][(j + z) % m]) % mod;
			}
		}
	}

	int ans = 0;
	for (int i = 1; i < n; i++)
	{
		ans = (ans + dp[i][0]) % mod;
	}

	for (int i = 1; i <= s[0] - '0'; i++)
	{
		dpe[0][i][i % m]++;
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j <= 9; j++)
		{
			for (int z = 0; z < m; z++)
			{
				if (j == s[i - 1] - '0')
				{
					for (int a = 0; a <= s[i] - '0'; a++)
					{
						dpe[i][a][(z + a) % m] = (dpe[i][a][(z + a) % m] + dpe[i-1][j][z]) % mod;
					}
				}
				else
				{
					for (int a = 0; a <= 9; a++)
					{
						dpe[i][a][(z + a) % m] = (dpe[i][a][(z + a) % m] + dpe[i - 1][j][z]) % mod;
					}
				}
			}
		}
	}

	for (int i = 0; i <= 9; i ++)
	{
		ans = (ans + dpe[n - 1][i][0]) % mod;
	}

	cout << ans;*/

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		a[i] = m;
	}

	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			dp[i][j] = oo;
		}
	}

	for (int i = 0; i < n; i++)
	{
		pref[i + 1] = pref[i] + a[i];
	}
	

	cout << rec(1, n);
	return 0;
}

Measured memory_bytes: 13824