#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define N 13
#define lb(t,i) lower_bound(t.begin(),t.end(),i)
using namespace std;
int n,l[N*N],imx=((1ll<<31)-1),sz[2];
ll s[N],ans,cur;
vector<int> ve[N*N],v[2];
mt19937 rng(time(0));
inline int rd(){
	return rng()&imx;
}

bool cmp(int aa,int bb){
	return s[aa%10]-s[aa/10-1]>s[bb%10]-s[bb/10-1];
}

inline ll val(int ss){
	return s[ss%10]-s[ss/10-1];
}

inline ll calc(){
	ll rt=0;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			rt+=s[j]-s[i-1];
//			printf("+ %d %d %lld\n",i,j,s[j]-s[i-1]);
			for(auto g:ve[10*i+j]) if(l[g]){
				rt-=val(g);
//				printf("- %lld\n",val(g));
				break;
			}
		}
	}
	return rt;
}

void SA(){
	cur=calc();
	ans=min(ans,cur);
//	printf("!!!\n");
	sz[0]=v[0].size();
	sz[1]=v[1].size();
//	printf("%lld\n",calc());
	for(double T=2e9;T>10;T*=0.9999){
		int i=rd()%sz[0],j=rd()%sz[1];
		swap(v[0][i],v[1][j]);
//		printf("%.3f %d %d %lld\n",T,v[0][i],v[1][j],calc());
		swap(l[v[0][i]],l[v[1][j]]);
		ll fz=calc();
		if(fz<=cur){
			cur=fz;
			ans=min(ans,cur);
			continue;
		}
		if(exp((double)(fz-cur)/T)>(double)rd()/imx) cur=fz;
		else swap(v[0][i],v[1][j]),swap(l[v[0][i]],l[v[0][j]]);
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],s[i]+=s[i-1];
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			for(int k=i;k<=j;k++){
				for(int o=k;o<=j;o++){
					ve[i*10+j].pb(k*10+o);
				}
			}
			sort(ve[i*10+j].begin(),ve[i*10+j].end(),cmp);
		}
	}
	for(int j=11;j<=99;j++){
		if(j%10>n||j%10<j/10) continue;
		v[0].pb(j);
	}
	for(int i=1;i<n*(n+1)/2;i++){
		sort(v[1].begin(),v[1].end());
		sort(v[0].begin(),v[0].end());
		for(int j=11;j<=99;j++) if(!l[j]){
			if(j%10>n||j%10<j/10) continue;
			l[j]=1;
			v[1].pb(j);
			v[0].erase(lb(v[0],j));
			break;
		}
//		printf("%d %d !\n",v[0].size(),v[1].size());
		ans=1e18;
		for(int j=1;j<=3;j++) SA();
		cout<<ans<<endl;
	}
	cout<<0;
	return 0;
}