#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rngll(high_resolution_clock::now().time_since_epoch().count());
template<typename T> T ctmax(T &x, const T &y){ return x = max(x, y); }
template<typename T> T ctmin(T &x, const T &y){ return x = min(x, y); }
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<int K = 2, typename T = long long, typename BO = plus<>, typename IO = minus<>>
struct subinterval{
	const array<int, K> N;
	BO bin_op;
	IO inv_op;
	const T id;
	vector<T> val, p;
	int pos(const array<int, K> &x){
		int res = 0;
		for(int i = 0; i < K; ++ i) res += p[i] * x[i];
		return res;
	}
	template<typename INIT>
	subinterval(const array<int, K> &N, INIT f, BO bin_op = plus<>{}, IO inv_op = minus<>{}, T id = 0LL): N(N), bin_op(bin_op), inv_op(inv_op), id(id), val(accumulate(N.begin(), N.end(), 1, [&](int x, int y){ return x * (y + 1); }), id), p(K + 1, 1){
		array<int, K> cur, from;
		partial_sum(N.begin(), N.end(), p.begin() + 1, multiplies<>{});
		cur.fill(1);
		while(1){
			T &c = val[pos(cur)];
			for(int i = 0; i < K; ++ i) -- cur[i];
			c = f(cur);
			for(int i = 0; i < K; ++ i) ++ cur[i];
			for(int mask = 1; mask < 1 << K; ++ mask){
				from = cur;
				for(int bit = 0; bit < K; ++ bit) if(mask & 1 << bit) -- from[bit];
				c = __builtin_popcount(mask) & 1 ? bin_op(c, val[pos(from)]) : inv_op(c, val[pos(from)]);
			}
			for(int i = 0; i < K; ++ i){
				if(++ cur[i] <= N[i]) break;
				if(i == K - 1) return;
				cur[i] = 1;
			}
		}
	}
	T query(const array<int, K> &low, const array<int, K> &high){
		T res = id;
		array<int, K> cur;
		for(int mask = 0; mask < 1 << K; ++ mask){
			for(int bit = 0; bit < K; ++ bit) cur[bit] = mask & 1 << bit ? low[bit] : high[bit];
			res = __builtin_popcount(mask) & 1 ? inv_op(res, val[pos(cur)]) : bin_op(res, val[pos(cur)]);
		}
		return res;
	}
	T query(const array<int, K> &high){
		return val[pos(high)];
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for(auto i = 0; i < n; ++ i){
		cin >> a[i];
	}
	subinterval<1, long long> sum({n}, [&](auto &x){ return a[x[0]]; });
	vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, numeric_limits<long long>::max()));
	for(auto i = 0; i < n; ++ i){
		dp[i][i + 1] = 0;
	}
	for(auto l = 2; l <= n; ++ l){
		for(auto i = 0; i + l <= n; ++ i){
			int j = i + l;
			for(auto k = i + 1; k < j; ++ k){
				ctmin(dp[i][j], dp[i][k] + dp[k][j] + sum.query({i}, {k}) + sum.query({k}, {j}));
			}
		}
	}
	cout << dp[0][n];
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Measured memory_bytes: 1536