#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define int long long

 const int N = ;

 int f[N][N], sum[N];

 main() {

     int n;

     scanf("%lld", &n);

     for(int i = ; i <= n; i++) {

         scanf("%lld", &sum[i]);

         sum[n + i] = sum[i];

     }

     memset(f, 0x3f, sizeof(f));

     for(int i = ; i <= n << ; i++) {

         sum[i] += sum[i - ];

         f[i][i] = ;

     }

     for(int len = ; len <= n; len++) {

         for(int l = ; l + len -  <= n << ; l++) {

             int r = l + len - ;

             for(int k = l; k < r; k++) {

                 f[l][r] = std::min(f[l][r], f[l][k] + f[k + ][r] + sum[r] - sum[l - ]);

             }

         }

     }

     int ans = 0x3f3f3f3f3f3f3f3f;

     for(int i = ; i <= n; i++) {

         ans = std::min(ans, f[i][i + n - ]);

     }

     printf("%lld\n", ans);

     memset(f, , sizeof(f));

     for(int len = ; len <= n; len++) {

         for(int l = ; l + len -  <= n << ; l++) {

             int r = l + len - ;

             for(int k = l; k < r; k++) {

                 f[l][r] = std::max(f[l][r], f[l][k] + f[k + ][r] + sum[r] - sum[l - ]);

             }

         }

     }

     ans = ;

     for(int i = ; i <= n; i++) {

         ans = std::max(ans, f[i][i + n - ]);

     }

     printf("%lld", ans);

     return ;

 }