def min(a, b)
  a < b ? a : b
end

def dfs(l, r)
  return @dp[l][r] if @used[l][r]
  @used[l][r] = true
  return 0 if l == r
  m = INF
  l.upto(r-1) do |i|
    m = min(m, dfs(l, i) + dfs(i+1, r))
  end
  return @dp[l][r] = m + @rui[r+1] - @rui[l]
end

INF = Float::INFINITY
N = gets.to_i
A = gets.split.map(&:to_i)

#4s近くかかる
#N = 400
#A = N.times.map{rand(1..(10**9))}
@dp = Array.new(N+1){Array.new(N+1, 0)}

@rui = Array.new(N+1,0)
1.upto(N) { |i| @rui[i] = @rui[i-1] + A[i-1] }

@used = Array.new(N){Array.new(N, false)}

p dfs(0, N-1)