CombiningRiceballs

import java.util.*;
import java.io.*;

public class CombiningRiceballs{

    static int[][] dp;
    static boolean[][] comb;

    public static void main (String[] args) throws IOException{
        readLine();
        int n = nextInt();

        dp = new int[n][n];
        comb = new boolean[n][n];

        readLine();
        for(int i = 0; i < n; i ++) {
            dp[i][i] = nextInt();
            comb[i][i] = true;
        }

        for(int d = 1; d < n; d ++) {
            for(int i = 0, j = d; j < n; i ++, j ++) {
                boolean found = false;
                for(int k = i; k < j && !found; k ++) {
                    if(comb[i][k] && comb[k + 1][j]) {
                        if(dp[i][k] != dp[k + 1][j]) {
                            dp[i][j] = Math.max(dp[i][j], Math.max(dp[i][k], dp[k + 1][j]));
                            comb[i][j] = false;
                        }else {
                            dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][j]);
                            comb[i][j] = true;
                            found = true;
                        }
                    }else {
                        dp[i][j] = Math.max(dp[i][j], Math.max(dp[i][k], dp[k + 1][j]));
                    }
                }

                for(int k = i; k < j && !found; k ++) {
                    for(int l = k + 1; l < j && !found; l ++) {
                        if(comb[i][k] && comb[k + 1][l] && comb[l + 1][j]) {
                            if(dp[i][k] == dp[l + 1][j]) {
                                dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k + 1][l] + dp[l + 1][j]);
                                comb[i][j] = true;
                                found = true;
                            }
                        }
                    }
                }
            }
        }

        System.out.println(dp[0][n - 1]);
    }
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static void readLine() throws IOException{
        st = new StringTokenizer(in.readLine());
    }
    static int nextInt() {
        return Integer.parseInt(st.nextToken());
    }
}