#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <string> #include <iomanip> #include <cmath> #include <queue> #include <map> #include <stack> #include <vector> using namespace std; #define long long LL const int N = 1e3+5; const int INF = 0x3f3f3f3f; int n,a[N],dp[N][N],minn = INF,sum[N],dp1[N][N],maxx; int main(){ cin >> n; memset(dp,INF,sizeof(dp)); for (int i = 1;i<=n;i++){ cin >> a[i]; a[i+n] = a[i]; } for (int i = 1;i<=2*n;i++){ sum[i] = sum[i-1] + a[i]; dp[i][i] = 0; } for (int i = 2;i<=n;i++){ for (int j = 1;j<=2*n-i+1;j++){ int endx = j + i - 1; for (int k = j;k<endx;k++){ dp[j][endx] = min(dp[j][endx],dp[j][k] + dp[k+1][endx] + sum[endx] - sum[j-1]); dp1[j][endx] = max(dp1[j][endx],dp1[j][k] + dp1[k+1][endx] + sum[endx] - sum[j-1]); } } } for (int i = 1;i<=n;i++){ minn = min(minn,dp[i][i+n-1]); maxx = max(maxx,dp1[i][i+n-1]); } cout << minn; return 0; }