#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 104;
int c[1002][1002];
int n,a[N],f[1002][1002],sum[N],ans = 999999999;
int main(){
	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> a[i];
	}
	for(int i = n + 1;i <= 2 * n;i++){
		a[i] = a[i - n];
	}
	for(int i = 1;i <= 2 * n;i++){
		sum[i] = sum[i - 1] + a[i];
	} 
	for(int i = 1;i < n;i++){
		for(int j = 1;j <= n - i + 1;j++){
			int end = i + j - 1;
			for(int k = j;k < end;k++){
				f[i][j] = min(f[i][k] + f[k + 1][j] + sum[end] - sum[j - 1],f[i][j]);
			}
			
		}
	}
	cout << f[1][n] << endl;
	for(int i = 1;i < n;i++){
		for(int j = 1;j <= n - i + 1;j++){
			int end = i + j - 1;
			for(int k = j;k <= end;k++){
				c[i][j] = max(c[i][k] + c[k + 1][j] + sum[end] - sum[j - 1],c[i][j]);
			}
			
		}
	}
	cout << c[1][n];
}