#include <bits/stdc++.h> 
 
using namespace std;  
 
typedef long long ll;  
typedef pair<int, int> ii;  
 
const int INF = 1e9;  
const ll LINF = 1e18;  
 
template<typename T>
bool minimize(T& a, const T& b) {
	if (b < a) {a = b; return true;} 
	return false;
}
 
// Tối ưu Knuth áp dụng cho các bài DP Range với công thức dp có dạng:
// dp(l, r) = min{dp(l, k) + dp(k + 1, r) + C(l, r)} (l <= k < r)
// Với hàm C thoả mãn các điều kiện sau với mọi a <= b <= c <= d:
// 1. C(b, c) <= C(a, d)
// 2. C(a, c) + C(b, d) <= C(a, d) + C(b, c) (bất đẳng thức tứ giác)
// (Tìm hiểu chi tiết hơn trong phần Tài liệu) 
const int N = 5e3 + 5; 
 
int n; 
int a[N]; 
ll pref[N];
 
ll getSum(int l, int r) {
	return pref[r] - pref[l - 1]; 
}
 
ll dp[N][N]; // dp[l][r] = Chi phí ít nhất để gộp các phần tử trong đoạn [l, r] về thành 1 phần tử
int opt[N][N]; // opt[l][r] = Điểm k (điểm cắt) tối ưu cho dp[l][r]
 
int main() {
	ios::sync_with_stdio(false); 
	cin.tie(nullptr); 	
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; 
		pref[i] = pref[i - 1] + a[i]; 
	}
 
	for (int l = n; l >= 1; l--) {
		for (int r = l; r <= n; r++) {
			if (l == r) {
				dp[l][r] = 0; 
				opt[l][r] = l;
				continue;  
			}
			dp[l][r] = LINF; 
			for (int k = opt[l][r - 1]; k <= opt[l + 1][r]; k++) {
				ll cost = getSum(l, r); 
				if (minimize(dp[l][r], dp[l][k] + dp[k + 1][r] + cost)) {
					opt[l][r] = k; 
				}
			}
		}
	}
 
	cout << dp[1][n] << '\n'; 
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsgIAoKdHlwZWRlZiBsb25nIGxvbmcgbGw7ICAKdHlwZWRlZiBwYWlyPGludCwgaW50PiBpaTsgIAoKY29uc3QgaW50IElORiA9IDFlOTsgIApjb25zdCBsbCBMSU5GID0gMWUxODsgIAoKdGVtcGxhdGU8dHlwZW5hbWUgVD4KYm9vbCBtaW5pbWl6ZShUJiBhLCBjb25zdCBUJiBiKSB7CglpZiAoYiA8IGEpIHthID0gYjsgcmV0dXJuIHRydWU7fSAKCXJldHVybiBmYWxzZTsKfQoKLy8gVOG7kWkgxrB1IEtudXRoIMOhcCBk4bulbmcgY2hvIGPDoWMgYsOgaSBEUCBSYW5nZSB24bubaSBjw7RuZyB0aOG7qWMgZHAgY8OzIGThuqFuZzoKLy8gZHAobCwgcikgPSBtaW57ZHAobCwgaykgKyBkcChrICsgMSwgcikgKyBDKGwsIHIpfSAobCA8PSBrIDwgcikKLy8gVuG7m2kgaMOgbSBDIHRob+G6oyBtw6NuIGPDoWMgxJFp4buBdSBraeG7h24gc2F1IHbhu5tpIG3hu41pIGEgPD0gYiA8PSBjIDw9IGQ6Ci8vIDEuIEMoYiwgYykgPD0gQyhhLCBkKQovLyAyLiBDKGEsIGMpICsgQyhiLCBkKSA8PSBDKGEsIGQpICsgQyhiLCBjKSAoYuG6pXQgxJHhurNuZyB0aOG7qWMgdOG7qSBnacOhYykKLy8gKFTDrG0gaGnhu4N1IGNoaSB0aeG6v3QgaMahbiB0cm9uZyBwaOG6p24gVMOgaSBsaeG7h3UpIApjb25zdCBpbnQgTiA9IDVlMyArIDU7IAoKaW50IG47IAppbnQgYVtOXTsgCmxsIHByZWZbTl07CgpsbCBnZXRTdW0oaW50IGwsIGludCByKSB7CglyZXR1cm4gcHJlZltyXSAtIHByZWZbbCAtIDFdOyAKfQoKbGwgZHBbTl1bTl07IC8vIGRwW2xdW3JdID0gQ2hpIHBow60gw610IG5o4bqldCDEkeG7gyBn4buZcCBjw6FjIHBo4bqnbiB04butIHRyb25nIMSRb+G6oW4gW2wsIHJdIHbhu4EgdGjDoG5oIDEgcGjhuqduIHThu60KaW50IG9wdFtOXVtOXTsgLy8gb3B0W2xdW3JdID0gxJBp4buDbSBrICjEkWnhu4NtIGPhuq90KSB04buRaSDGsHUgY2hvIGRwW2xdW3JdCgppbnQgbWFpbigpIHsKCWlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgCgljaW4udGllKG51bGxwdHIpOyAJCgljaW4gPj4gbjsKCWZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewoJCWNpbiA+PiBhW2ldOyAKCQlwcmVmW2ldID0gcHJlZltpIC0gMV0gKyBhW2ldOyAKCX0KCglmb3IgKGludCBsID0gbjsgbCA+PSAxOyBsLS0pIHsKCQlmb3IgKGludCByID0gbDsgciA8PSBuOyByKyspIHsKCQkJaWYgKGwgPT0gcikgewoJCQkJZHBbbF1bcl0gPSAwOyAKCQkJCW9wdFtsXVtyXSA9IGw7CgkJCQljb250aW51ZTsgIAoJCQl9CgkJCWRwW2xdW3JdID0gTElORjsgCgkJCWZvciAoaW50IGsgPSBvcHRbbF1bciAtIDFdOyBrIDw9IG9wdFtsICsgMV1bcl07IGsrKykgewoJCQkJbGwgY29zdCA9IGdldFN1bShsLCByKTsgCgkJCQlpZiAobWluaW1pemUoZHBbbF1bcl0sIGRwW2xdW2tdICsgZHBbayArIDFdW3JdICsgY29zdCkpIHsKCQkJCQlvcHRbbF1bcl0gPSBrOyAKCQkJCX0KCQkJfQoJCX0KCX0KCgljb3V0IDw8IGRwWzFdW25dIDw8ICdcbic7IAp9

NQoyIDcgMyAyIDU=

5
2 7 3 2 5