#define INPUT "./io/test.in"
#define OUTPUT "./io/test.out"
#ifdef NARUT_LOCAL
	#include "local.hpp"
	#include "reopen.hpp"
	#else
	#pragma GCC optimize("-O2", "-ftree-vectorize")
	#include <algorithm>
	#include <array>
	#include <bitset>
	#include <cassert>
	#include <cctype>
	#include <cmath>
	#include <complex>
	#include <cstdint>
	#include <cstdio>
	#include <cstdlib>
	#include <cstring>
	#include <deque>
	#include <exception>
	#include <functional>
	#include <initializer_list>
	#include <iomanip>
	#include <iostream>
	#include <iterator>
	#include <limits>
	#include <list>
	#include <locale>
	#include <map>
	#include <memory>
	#include <numeric>
	#include <queue>
	#include <random>
	#include <set>
	#include <sstream>
	#include <stack>
	#include <stdexcept>
	#include <tuple>
	#include <type_traits>
	#include <utility>
	#include <vector>
	using namespace std;
	#define DBG(...)
	#define DBG2(...)
	#define Debug(...)
	#define TM_(...) template <class __VA_ARGS__>
	#define ENABLE(...) TM_(T) static enable_if_t<__VA_ARGS__>
	#define SFINAE(name, ...)                                                                \
		TM_(, class = void) struct name##_s : false_type {};                                 \
		TM_(T) struct name##_s<T, decltype(void(__VA_ARGS__))> : true_type {};               \
		TM_(T) constexpr auto name = name##_s<T>::value;
	namespace narut {
	TM_(T) using TupSz = tuple_size<decay_t<T>>;
	SFINAE(Iterable, begin(declval<T &>()))
	SFINAE(IsTuple, TupSz<T>{})
	SFINAE(Coutable, cout << declval<T &>())
	SFINAE(Cinable, cin >> declval<T &>())
	TM_(, class = void) struct Spc { static const char val = '\n'; };
	TM_(T) struct Spc<T, enable_if_t<Coutable<T>>> { static const char val = ' '; };
	struct Ctx {
		ENABLE(Coutable<T>) Write(T const &t) { cout << t; }
		ENABLE(!Coutable<T> and Iterable<T>) Write(T const &t) {
			auto it = begin(t), e = end(t);
			if (it != e) Write(*it++);
			for (; it != e; Write(*it++)) cout << Spc<decltype(*it)>::val;
		}
		TM_(T, size_t... Is)
		static void WriteTup(T const &t, index_sequence<Is...>) {
			(void)(int[]){0, ((Is == 0) ? 0 : ((cout << ' '), 0), Write(get<Is>(t)), 0)...};
		}
		ENABLE(!Coutable<T> and !Iterable<T> and IsTuple<T>) Write(T const &t) {
			WriteTup(t, make_index_sequence<TupSz<T>::value>{});
		}
		ENABLE(Cinable<T>) Read(T &t) { cin >> t; }
		ENABLE(!Cinable<T> and Iterable<T>) Read(T &t) {
			for (auto &&x : t) Read(x);
		}
		TM_(T, size_t... Is) static void ReadTup(T &t, index_sequence<Is...>) {
			(void)(int[]){0, (Read(get<Is>(t)), 0)...};
		}
		ENABLE(!Cinable<T> and !Iterable<T> and IsTuple<T>) Read(T &t) {
			ReadTup(t, make_index_sequence<TupSz<T>::value>{});
		}
	};
	void Cout() { cout << '\n'; }
	TM_(F, class... Ts) void Cout(F const &f, Ts const &... ts) {
		Ctx::Write(f);
		(void)(int[]){0, (cout << ' ', Ctx::Write(ts), 0)...};
		cout << '\n';
	}
	TM_(T) T Cin() {
		T t;
		Ctx::Read(t);
		return t;
	}
	TM_(T) void Cin(T &t) { Ctx::Read(t); }
	TM_(T) void Cin(T &t, int n) {
		t.resize(n);
		Ctx::Read(t);
	}
	TM_(T) struct Big {
		constexpr operator T() const {
			T x = 0, mask = 0x3f;
			for (int i = 0; i < sizeof(T); i++) x |= mask << 8 * i;
			return x;
		}
	};
	} // namespace narut
	using narut::Big;
	using narut::Cin;
	using narut::Cout;
	using ll = long long;

	using uint = unsigned int;
#endif



int n;

vector<vector<ll> > dp, sm;
vector<int> A;

auto Run() {
	cin>>n;
	Cin(A,n);
	sm.resize(n+1, vector<ll> (n+1));
	dp.resize(n+1, vector<ll> (n+1));


	for (int i = 0; i < n; i++) {
		sm[i][i+1] = A[i];
	}

	for (int s = 2; s <= n; s++) {
		for (int i = 0; i < n; i++) {
			int e = i+s;
			if (e > n) break;
			ll mn = Big<ll>{};
			for (int j = i+1; j < i+s; j++) {
				mn = min(mn, dp[i][j] + dp[j][e]);
			}
			sm[i][e] = sm[i][i+1] + sm[i+1][e];
			dp[i][e] = mn + sm[i][e];
		}
	}
	// Debug(sm);
	cout << dp[0][n];	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(10);

	Run();
}



Measured memory_bytes: 2816