#include<bits/stdc++.h>
using namespace std;
int a[800000],sum[800000];
int op[8000][8000];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		op[i][i]=0;
		
	}
	for(int len=2;len<=n;len++){
		for(int qi=1;len+qi-1<=n;qi++){
			int mo=qi+len-1; 
			op[qi][mo]=1e8;
			for(int i=qi;i<mo;i++){
				op[qi][mo]=min(op[qi][i]+op[i+1][mo]+sum[mo]-sum[qi-1],op[qi][mo]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<op[i][j];
		}
		puts("");
	}
	cout<<op[1][n];
	puts("");
	for(int len=2;len<=n;len++){
		for(int qi=1;len+qi-1<=n;qi++){
			int mo=qi+len-1; 
			op[qi][mo]=-1;
			for(int i=qi;i<mo;i++){
				op[qi][mo]=max(op[qi][i]+op[i+1][mo]+sum[mo]-sum[qi-1],op[qi][mo]);
			}
		}
	}
	cout<<op[1][n];
	
}