class Slime
  attr_accessor :cost, :size
  def initialize(cost,size)
    @cost = cost
    @size = size
  end
  
  def +(other)
    Slime.new(size + other.size + cost + other.cost, size + other.size)
  end

  def >(other)
    cost > other.cost
  end
end

INF = Slime.new(1<<60, 0)

class DP
  attr_accessor :n, :a, :dp
  def initialize
    @n = gets.to_s.to_i
    @a = gets.to_s.split.map{ |v| Slime.new(0, v.to_i) }
    @dp = Array.new(n){ Array.new(n, nil) }
  end

  # [lo,hi] 閉区間
  def rec(lo,hi)
    return dp[lo][hi] if dp[lo][hi] != nil
    return dp[lo][hi] = a[lo] if hi - lo == 0
    return dp[lo][hi] = a[lo] + a[hi] if hi - lo == 1

    cur = INF
    lo.upto(hi-1) do |mid|
      n_slime = rec(lo,mid) + rec(mid+1,hi)
      cur = n_slime if cur > n_slime
    end
    dp[lo][hi] = cur
  end

  def solve
    rec(0,n-1)
  end
end

p DP.new.solve.cost