import std.stdio, std.conv, std.string, std.bigint;
import std.math, std.random, std.datetime;
import std.array, std.range, std.algorithm, std.container, std.format;
string read(){ static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res; }

/*

----------------------------------------

i番目から、j番目の前までを1つにするのにかかるコストの最小値をx[i, j]

x[i, j] = (sum[j] - sum[i]) + min(k; i .. j) (x[i, k] + x[k, j])

ただし　x[i, i] = 0

求めるものは　x[0, n]

----------------------------------------

上記だとメモ化再帰になってしまいやりづらい

長さがiで、左端がjである区間を1つにするのにかかるコストの最小値をx[i, j]
※先程のiは今のj、先程のjは今のj + i

x[i, j] = (sum[i + j] - sum[j]) + min(k; 1 .. i) (x[k, j] + x[i - k, j + k])

ただし　x[1, j] = 0

sum[i] はiの前までの和

求めるものは　x[n, 0]

*/

const long infty = 400 * 400 * 1_000_000_000 * 10;

void main(){
 int n = read.to!int;
 
 long[] as = readln.chomp.split.map!(to!long).array;
 
 long[] sums = [0];
 foreach(a; as) sums ~= sums[$ - 1] + a;
 
 long[][] xs = [[]];
 foreach(i; 1 .. n + 1){
	 xs ~= [[]];
	 foreach(j; 0 .. n + 1 - i){
		 if(i == 1) xs[i] ~= 0;
		 else{
			 long m = long.max;
			 foreach(k; 1 .. i){
				 m = min(m, xs[k][j] + xs[i - k][j + k]);
			 }
			debug writeln("i:", i, " j:", j, " m:", m);
			 xs[i] ~= sums[i + j] - sums[j] + m;
		 }
		debug writeln("i:", i, " xs[i]:", xs[i]);
	 }
 }
 
 xs[n][0].writeln;
 
 
}
