#include <iostream>
#include <iomanip>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <iterator>
#include <functional>
#include <limits>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <cstring>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 

// using namespace __gnu_pbds; 
using namespace std;

//macros
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ld long double
#define pb push_back
#define f first
#define s second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define watch(x) cout << "debug : " << #x << " -> " << x << endl; 

//globals
ll const mod = 1e9+7;
ll const size_1d = 1e6 + 7;
ll const size_2d = 1e3 + 7;
ll const inf = 1e18;

//functions
ll power(ll x, ll y, ll mod = 2e18){ ll ans = 1;x %= mod;while(y){if(y&1)ans = (x * ans) % mod;x = (x * x) % mod;y >>= 1;}return ans;}
ll modInverse(ll a, ll m){ll m0 = m;ll y = 0, x = 1;if (m == 1) return 0;while (a > 1){ ll q = a / m;ll t = m;m = a % m,a = t;t = y;y = x - q * y;x = t;}if(x < 0) x += m0;return x;} 
ll gcdext(ll a,ll b,ll *x = 0, ll *y = 0){if(a == 0){*x = 0;*y = 1;return b;}ll x1,y1;ll gcd1 = gcdext(b%a,a,&x1,&y1);*x = y1 - (b/a)*x1;*y = x1;return gcd1;}
int randomize(){return (rand()%10000);} 

// CODE STARTS HERE

int main() {
  IOS;

  int n;cin >> n;
  ll dp[n+1][n+1];
  ll dp2[n+1][n+1];
  for (int i = 0; i <= n; ++i)
  {
    for (int j = 0; j <= n; ++j)
    {
      dp[i][j] = inf;
      dp2[i][j] = inf;
    }
  }
  std::vector<ll> v(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> v[i];
  }
  for (int i = 1; i < n; ++i)
  {
    dp[i][i+1] = v[i-1] + v[i];
    // dp2[i][i+1] = v[i-1] + v[i];
  }
  for (int i = 0; i < n; ++i)
  {
    dp2[i+1][i+1] = 0;
    dp[i+1][i+1] = v[i];
  }
  for (int i = 1; i <= n; ++i)
  {
    for (int j = 1; j <= n; ++j)
    {
      if(i + j > n)
        break;
      for (int k = j; k < i + j; ++k)
      {
        // if(k == j){
          if((dp2[j][k] + dp[j][k] + dp[k+1][j + i]+ dp2[k + 1][i + j]) < dp2[j][j+i]){
            dp[j][j + i] = dp[j][k] + dp[k+1][j + i];
            dp2[j][j + i] =(dp2[j][k] + dp[j][j + i]+ dp2[k + 1][i + j]);  
          }
        // }
        // else if(k + 1 == i + j){
        //   if((dp2[j][k] + dp[j][k] + dp[k+1][j + i]+ dp2[k + 1][i + j]) > dp2[j][j+i]){
        //     dp[j][j + i] = dp[j][k] + dp[k+1][j + i];
        //     dp2[j][j + i] = max((dp[j][i] + dp2[k + 1][i + j] + dp2[k+1][i+j]),dp2[j][i+j]);  
        //   }
        //   dp2[j][j + i] = max(2*dp2[j][k] + dp2[k + 1][i + j],dp2[j][i+j]);
        // }
        // else
        //   dp2[j][j + i] = max((2*dp2[j][k] + 2*dp2[k + 1][i + j]),dp[j][j + i]); 
      }
    }
  }
  // for (int i = 0; i <= n; ++i)
  // {
  //   for (int j = 0; j <= n; ++j)
  //   {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // for (int i = 0; i <= n; ++i)
  // {
  //   for (int k = 0; k <= n; ++k)
  //   {
  //     cout << dp2[i][k] << " ";
  //   }
  //   cout << endl;
  // }
  cout << dp2[1][n] << endl;

  return 0;
}

Measured memory_bytes: 2816