1 枚举len
2 枚举l
3 松弛操作
// author:leimingze
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define _ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define LL long long
#define ULL unsigned unsigned
#define PII pair<int,int>
#define MOD 1e9+7
#define INF 0x3f3f3f3f
#define eps 1e-8
const double PI = acos(-1.0);
const int dx4[4] = { 0,-1,0,1 };
const int dy4[4] = { -1,0,1,0 };
//#pragma warning(disable:4786)//使命名长度不受限制
//#pragma comment(linker, "/STACK:102400000,102400000")//手工开栈
int qmi(int a, int k, int p) { int res = 1 % p; while (k) { if (k & 1)res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; }return res; }
template <typename T> void inline read(T& x)
{
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
//不开long long 见祖宗,递归剪枝
const int N = 410;
int f[N][N], g[N][N];
int n;
int w[N];
int s[N];//前缀和
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> w[i], w[n + i] = w[i];
for (int i = 1; i <= n << 1; i++)s[i] = s[i - 1] + w[i];
memset(f, 0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
for (int len = 1; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n << 1; l++)
{
int r = l + len - 1;
if (l == r)f[l][r] = g[l][r] = 0;
else
{
for (int k = l; k + 1 <= r; k++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
}
}
}
}
int maxv = -INF, minv = INF;
for (int i = 1; i <= n; i++)
{
minv = min(minv, f[i][i + n - 1]);
maxv = max(maxv, g[i][i + n - 1]);
}
cout << minv << endl;
cout << maxv << endl;
}
int main()
{
solve();
return 0;
}