#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const long long LLINF = 0x3f3f3f3f3f3f3f3fLL;
int a[N], sum[N], dp1[N][N], dp2[N][N];
int main(){
	int n;
	cin >> n;
	memset(dp1, 0x3f, sizeof(dp1));
	memset(dp2, 0, sizeof(dp2));
	for(int i = 1 ; i <= n ; i++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= n ; i++){
		sum[i] = sum[i - 1] + a[i];
		dp1[i][i] = 0;
		dp2[i][i] = 0;
	}
	for(int i = 2 ; i <= n ; i++){
		for(int l = 1, r = i ; r <= n ; l++, r++){
			for(int k = l ; k < r ; k++){
				dp1[l][r] = min(dp1[l][r], dp1[l][k] + dp1[k + 1][r] + sum[r] - sum[l - 1]);
				dp2[l][r] = max(dp2[l][r], dp2[l][k] + dp2[k + 1][r] + sum[r] - sum[l - 1]);
			} 
		}
	}
	cout << dp1[1][n] << endl;
	return 0;
}