// Original C++ solution (slower):
/*

 * atcoder/dp/n.cpp

 */



// C++ 14

#include <iostream>

#include <string>

#include <vector>

#include <list>

#include <algorithm>

#include <queue>

#include <stack>

#include <set>

#include <map>

#include <unordered_map>

#include <math.h>

#include <cstring>



#define ll long long

#define Int ll

#define loop(__x, __start, __end) for(Int __x = __start; __x < __end; __x++)

#define loopdown(__x, __start, __end) for(Int __x = __start; __x > __end; __x--)

#define rep(__n) for(Int __x = 0; __x < __n; __x++)

#define span(__a,__x,__y) __a.begin()+__x,__a.begin()+__y

#define span_all(__a) __a.begin(),__a.end()

#define len(__x) (__x.size())

#define last(__x) (__x[__x.size()-1])



using namespace std;



template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }

template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }





struct Point {

  Int x, y;

  Point(Int x, Int y): x(x), y(y) {}

  Point(): x(0), y(0) {}



  Point operator + (Point v) { return Point(x + v.x, y + v.y); }

  Point operator - (Point v) { return Point(x - v.x, y - v.y); }

  bool operator == (const Point &v) const {

    return x == v.x && y == v.y;

  }

  bool operator< (const Point &p1) const {

    return x < p1.x && y < p1.y;

  }

};

ostream & operator << (ostream & out, Point const & v) {

  out << "Point(" << v.x << ", " << v.y << ')';

  return out;

}



istream & operator >> (istream & in, Point & v) {

  Int x, y;

  in >> x; in >> y; v.x = x; v.y = y;

  return in;

}



// Geometry



#define EPS 0.0000000001



class Vector2 {

public:

  double x, y;

  

  Vector2(double x = 0, double y = 0): x(x), y(y) {}

  

  Vector2 operator + (Vector2 v) { return Vector2(x + v.x, y + v.y); }

  Vector2 operator - (Vector2 v) { return Vector2(x - v.x, y - v.y); }

  Vector2 operator * (double k) { return Vector2(x * k, y * k); }

  Vector2 operator / (double k) { return Vector2(x / k, y / k); }

  

  double length() { return sqrt(norm()); }

  double norm() { return x * x + y * y; }

  double dot (Vector2 v) { return x * v.x + y * v.y; }

  double cross (Vector2 v) { return x * v.y - y * v.x; }

  

  bool operator < (const Vector2 &v) const {

    return x != v.x ? x < v.x : y < v.y;

  }

  

  bool operator == (const Vector2 &v) const {

    return fabs(x - v.x) < EPS && fabs(y - v.y) < EPS;

  }

};



ostream & operator << (ostream & out, Vector2 const & v) { 

  out<< "Vector2(" << v.x << ", " << v.y << ')';

  return out;

}



istream & operator >> (istream & in, Vector2 & v) { 

  double x, y;

  in >> x;

  in >> y;

  v.x = x;

  v.y = y;

  return in;

}





vector<Int> slice(vector<Int> &vec, int s, int t) {

  return vector<Int>(vec.begin()+s, vec.begin()+t);

}



vector<Int> trim(vector<Int> &vec, int n) {

  auto init = slice(vec, 0, n);

  auto tail = slice(vec, n+2, vec.size());

  init.insert(init.end(), tail.begin(), tail.end());

  return init;

}





Int N;

vector<Int> A;



void input() {

  cin >> N;

  Int a;

  loop(n,0,N) {

    cin >> a;

    A.push_back(a);

  }

}



const Int INFTY = 100000000000000000;

Int dp[410][410];

Int acc[410];



void dump() {

  loop(j,0,N+1) {

    loop(i,0,N+1) {

      cout << dp[i][j] << " ";

    }

    cout << endl;

  }

}



Int rec(Int l, Int r) {

  Int &cache = dp[l][r];

  if (~cache) return cache;

  if (r-l<=1) return cache = 0;

  Int self = acc[r] - acc[l];

  Int child = INFTY;

  loop(cut,l+1,r) {

    chmin(child, rec(l, cut) + rec(cut, r));

  }

  return cache = self + child;

}



Int memoRec() {

  memset(dp, -1, sizeof(dp));

  acc[0] = 0;

  loop(n,0,N) acc[n+1] = acc[n] + A[n];

  return rec(0, N);

}



void solve() {

  Int r = memoRec();

  cout << r << endl;

}



int main() {

  // cout.precision(15);

  input();

  solve();

  return 0;

}


// Optimized solution to the same problem (faster):
/*

 * atcoder/dp_2nd/n.cpp

 */



// C++ 14

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring> // memset

#include <cassert>



using namespace std;



#define ll long long

#define MOD 1000000007



#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }

template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }



const int MAX = 420;

const ll INF = 100000000000000000;

ll N;

vector<ll> A;



// [l: r) までを合体させる最小コスト

ll dp[MAX][MAX];



void input() {

  cin >> N;

  ll a;

  loop(n,0,N) {

    cin >> a;

    A.push_back(a);

  }

}



void solve() {

  for (int len=1; len<=N; len++) {

    for (int l=0; l+len<=N; l++) {

      if (len == 1) { dp[l][l+1] = 0; continue; }

      ll self = 0, child = INF;

      int r = l+len;

      for (int i=l; i<r; i++) self += A[i];

      for (int cut=l+1; cut<r; cut++) {

        chmin(child, dp[l][cut] + dp[cut][r]);

      }

      dp[l][r] = self + child;

    }

  }

  cout << dp[0][N] << endl;

}



void dump() {

  for (int len=1; len<=N; len++) {

    for (int l=0; l+len<=N; l++) {

      cout << "[" << l << ": " << (l+len-1) << "] dp = " << dp[l][l+len] << endl;

    }

  }

}



int main() {

  // cout.precision(15);

  input();

  solve();

  // dump();

  return 0;

}


// Fastest known solution for this problem: