#include <bits/stdc++.h>
using namespace std;
vector<long long> V;
vector<vector<long long>> DP;
vector<long long> P;
long long getSum(int start, int end) { return P[end + 1] - P[start]; }
long long solve(int start, int end) {
  long long& dp = DP[start][end];
  if (dp != -1) {
    return dp;
  }
  int length = end - start + 1;
  if (length == 1) {
    return dp = 0;
  }
  if (length == 2) {
    return (dp = (V[start] + V[end]));
  }
  long long ans = INT64_MAX;
  for (int i = start; i < end; i++) {
    long long tmp = solve(start, i) + solve(i + 1, end);
    ans = min(tmp, ans);
  }
  return dp = ans + getSum(start, end);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  V = vector<long long>(n);
  DP = vector<vector<long long>>(n, vector<long long>(n, -1));
  P = vector<long long>(n + 1);
  for (auto& v : V) cin >> v;
  for (int i = 1; i <= n; i++) {
    P[i] = P[i - 1] + V[i - 1];
  }
  long long ans = solve(0, n - 1);
  cout << ans;
  return 0;
}
