//HDOJ 3506

 #include<cmath>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #define rep(i,n) for(int i=0;i<n;++i)

 #define F(i,j,n) for(int i=j;i<=n;++i)

 #define D(i,j,n) for(int i=j;i>=n;--i)

 #define pb push_back

 #define CC(a,b) memset(a,b,sizeof(a))

 using namespace std;

 int getint(){

     int v=,sign=; char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}

     while(isdigit(ch))  {v=v*+ch-''; ch=getchar();}

     return v*sign;

 }

 const int N=;

 const int INF=;

 const double eps=1e-;

 /*******************template********************/

 int s[N][N],a[N];

 int dp[N][N];

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("input.txt","r",stdin);

 //    freopen("output.txt","w",stdout);

 #endif

     int n;

     while(scanf("%d",&n)!=EOF && n){

         CC(a,);CC(s,);

         F(i,,n) a[i+n]=a[i]=getint();

         F(i,,n<<) a[i]+=a[i-];

         F(i,,n*-){

             dp[i][i+]=a[i+]-a[i-];

             s[i][i+]=i;

         }

         F(len,,n)

             F(i,,n*-len+){

                 int j=i+len-;

                 dp[i][j]=INF;

                 F(k,s[i][j-],s[i+][j]){

                     int tmp=dp[i][k]+dp[k+][j]+a[j]-a[i-];

                     if (tmp<dp[i][j]){

                         dp[i][j]=tmp;

                         s[i][j]=k;

                     }

                 }

             }

         int ans=INF;

         F(i,,n) ans=min(ans,dp[i][i+n-]);

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

     }

     return ;

 }