// UUID: 7ab6df8b-4955-4969-bf0d-a59c80859422
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
	cin >> n;
	vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));
	vector<vector<int>> cost(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i][i];
	}
	for	(int i = 0; i < n; i++)
	{
		for (int j = i+1; j < n; j++)
		{
			cost[i][j] = max(cost[i][j-1], cost[j][j]);
		}
	}

	for(int h = 0; h < n; h++){
		for(int i = 0; i + h < n; i++){
			int j = i + h;
			if(h == 0){
				dp[i][i] = 0;
				continue;
			}
			if(h == 1){
				dp[i][i + 1] = min(cost[i][i], cost[i + 1][i + 1]);
				continue;
			}
			for(int l = i; l <= j; l++){
				for(int r = l; r <= j; r++){
					dp[i][j] = min(dp[i][j], max(dp[i][max(l - 1, i)], max(dp[l][r], dp[min(r + 1, j)][j])) + cost[l][r]);
				}
			}
		}
	}

	for	(int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			//cout << dp[i][j] << " ";
		}
		//cout << "\n";
	}

	cout << dp[0][n - 1];
}