#include <bits/stdc++.h>
using namespace std;
int n, minn = 1e9, maxn = -1e9, a[105], dp[205][205], dp2[205][205], s[105];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		a[i + n] = a[i];
	}
	for(int i = 1; i <= 2 * n; i++){
		s[i] = s[i - 1] + a[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	for(int i = 1; i <= n * 2; i++)dp[i][i] = 0;
	for(int len = 2; len <= n; len++){
		for(int l = 2; l + len - 1 <= 2 * n; l++){
			int r = l + len - 1;
			for(int k = l; k < r; k++)
				dp[l][r] = min(dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1], dp[l][r]);
		}
	}
	for(int i = 1; i <= n; i++)minn = min(minn, dp[i][i + n - 1]);
	for(int len = 2; len <= n; len++){
		for(int l = 1; l + len - 1 <= n * 2; l++){
			int r = l + len - 1;
			for(int k = l; k < r; k++)
				dp2[l][r] = max(dp2[l][k] + dp2[k + 1][r] + s[r] - s[l - 1], dp2[l][r]);
		}
	}
	for(int i = 1; i <= n; i++)maxn = max(maxn, dp2[i][i + n - 1]);
	cout << minn << '\n' << maxn;
	return 0;
}

#3数据

in:

78
4 4 10 13 7 1 16 7 0 7 19 7 9 14 18 1 5 17 1 8 11 19 15 18 11 12 2 3 7 1 13 0 17 10 2 5 1 7 1 10 7 0 12 10 9 10 9 18 11 11 7 8 6 10 7 18 1 11 2 3 18 9 17 17 10 14 16 1 4 7 1 5 11 3 13 17 7 0 

out:

4084
28949

(话说在洛谷IDE和本地运行#3的结果是一样的，并且还正确 结果这里错了是为嘛)