#include <bits/stdc++.h>
#define LOCAL
using std::to_string;
auto to_string(std::string s) -> std::string {
  return '"' + s + '"';
}
auto to_string(char c) -> std::string {
  return "'" + std::string{c} + "'";
}
auto to_string(const char* s) -> std::string {
  return to_string((std::string) s);
}
auto to_string(bool b) -> std::string {
  return (b ? "true" : "false");
}
template <typename T, typename U>
auto to_string(std::pair<T, U> p) -> std::string {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <size_t N>
auto to_string(std::bitset<N> bs) -> std::string {
  std::string res{};
  for (size_t i = 0; i < N; i++)
    res.insert(res.begin(), bs.test(i) ? '1' : '0');
  return res;
}
template <typename T>
auto to_string(T v) -> std::string {
  bool flg = false;
  std::string res = "{";
  for (auto const&x : v) {
    if (flg) res += ", ";
    else flg = true;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  std::cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
template<typename T, typename U>
inline auto cmn (T& a, U b) {if (a > b) {a = b; return true;} return false;}
template<typename T, typename U>
inline auto cmx (T& a, U b) {if (a < b) {a = b; return true;} return false;}
int main() {
  std::cin.tie(0); std::cin.sync_with_stdio(false);
  int n; std::cin >> n;
  std::vector<long long>a(n);
  std::for_each(a.begin(), a.end(), [](auto& x){std::cin >> x;});
  using value_t = std::pair<long long, long long>;
  using vec1    = std::vector<value_t>;
  using vec2    = std::vector<vec1>;
  using vec3    = std::vector<vec2>;
  auto dp = vec3(n, vec2(n));
  auto insert = [&] (vec1& v, long long x, long long y) {
    assert(std::is_sorted(v.begin(), v.end(), [](auto p, auto q){
      return p.first < q.first;
    }));
    auto lb = std::lower_bound(v.begin(), v.end(), value_t{x, 0LL});
    if (lb != v.begin()) {
      auto it = std::prev(lb);
      if (it->second <= y) return;
    }
    auto it = lb;
    while (it != v.end() && y <= it->second) it = v.erase(it);
    v.insert(it, {x, y});
    assert(std::is_sorted(v.begin(), v.end(), [](auto p, auto q){
      return p.first < q.first;
    }));
  };
  auto renew = [&] (int l, int r) {
    assert(0 <= l && l <= r && r < n);
    for (int c = l + 1; c < r; c++) {
      for (auto p : dp.at(l).at(c)) {
        for (auto q : dp.at(c).at(r)) {
          insert(dp.at(l).at(r),
            p.first + p.second + a.at(c) + q.first,
            p.second + a.at(c) + q.first + q.second
          );
        }
      }
    }
  };
  for (int i = 0; i < n - 1; i++) {
    dp.at(i).at(i + 1).emplace_back(0, 0);
  }
  for (int d = 2; d < n; d++) {
    for (int l = 0, r = d; r < n; l++, r++) {
      renew(l, r);
    }
  }
  constexpr long long inf = 1LL << 60;
  long long ret = inf;
  for (auto p : dp.at(0).at(n - 1)) {
    cmn(ret,
      a.at(0) + p.first + p.second + a.at(n - 1)
    );
  }
  std::cout << ret << std::endl;
  return 0;
}

Measured memory_bytes: 384