n = gets.to_i
@a = gets.split.map(&:to_i)

@a << 0
(n-1).times {|i| @a[i+1] += @a[i]}

INF = 1 << 50

@memo = Array.new(n) {Array.new(n)}

def calc(l, r)
    return @memo[l][r] if @memo[l][r]
    return @memo[l][r] = 0 if l == r

    t = INF
    l.upto(r-1) do |i|
        u = calc(l, i) + calc(i+1, r)
        t = u if t > u
    end

    @memo[l][r] = @a[r] - @a[l-1] + t
end

p calc(0, n-1)