import java.io.*;
import java.util.Scanner;
public class Problem3_3 {
public static void main(String [] args) throws IOException {
File inputfile = new File("input.txt");
File outputfile= new File("output.txt");
Scanner input = new Scanner(inputfile);
PrintWriter output = new PrintWriter(outputfile);
int sum = input.nextInt();
int stones [] = new int [sum+1];
for(int i=1;i<=sum;i++)
stones[i] = input.nextInt();
int min = assign_Of_Min(sum,stones);
System.out.println();
int max = assign_Of_Max(sum,stones);
output.println(min);
System.out.println();
output.println(max);
input.close();
output.close();
System.out.println("结束");
}
public static int assign_Of_Min(int n,int [] arrays) {
int [][] matrix = new int [n+1][n+1];
for(int i=1;i<=n;i++)
matrix[i][i]=arrays[i];
for(int i=2;i<=n;i++) {
for(int j=1;j<=n-i+1;j++) {
int z = i+j-1;
matrix[j][z] = matrix[j][j]+scores(j,z,j,arrays)+matrix[j+1][z]; //+matrix[j+1][z]+
int p;
for(int k=j+1;k<z;k++) {
p = scores(j,z,k,arrays)+matrix[j][k]+matrix[k+1][z];//+matrix[k+1][z]
if(p<matrix[j][z])
matrix[j][z]=p;
}
}
}
showMatrix(matrix);
return matrix[1][n];
}
public static int assign_Of_Max(int n,int [] arrays) {
int [][] matrix = new int [n+1][n+1];
for(int i=1;i<=n;i++)
matrix[i][i]=arrays[i];
for(int i=2;i<=n;i++) {
for(int j=1;j<=n-i+1;j++) {
int z = i+j-1;
matrix[j][z] = matrix[j][j]+scores(j,z,j,arrays)+matrix[j+1][z]; //+matrix[j+1][z]+
int q;
for(int k=j+1;k<z;k++) {
q = scores(j,z,k,arrays)+matrix[j][k]+matrix[k+1][z];//+matrix[k+1][z]
if(q>matrix[j][z])
matrix[j][z]=q;
}
}
}
showMatrix(matrix);
return matrix[1][n];
}
public static int scores(int low,int high,int k,int [] scores) {
if(low<1||high>scores.length-1) {
System.out.println("you input is wrong");
return 0;
}
else {
if(low==high)
return 0;
else if(low+1==high)
return 0;
else {
int sumofLeft,sumOfRight;
sumofLeft=sumOfRight=0;
if(low==k)
sumofLeft=0;
else{
for(int i=low;i<=k;i++) {
sumofLeft += scores[i];
}
}
if(k+1==high)
sumOfRight=0;
else{
for(int j=k+1;j<=high;j++){
sumOfRight += scores[j];
}
}
return sumOfRight+sumofLeft;
}
}
}
public static void showMatrix(int [][] array){
for(int i=1;i<array.length;i++){
for(int j=1;j<array[i].length;j++)
System.out.printf("- ",array[i][j]);
System.out.println();
}
}
}
