# Parallel?

n = gets.to_i
ps = gets.split(' ').map(&:to_i)

sum = 0
memos = {}

1.upto(n - 1) do |diff|
  1.upto(n - diff) do |l|
    r = l + diff
    memo = memos["#{l}#{r - 1}"]
    pr = ps[r - 1]
    if memo
      if pr < memo[0]
        memos["#{l}#{r}"] = memo
        sum += memo[0]
      elsif memo[1] < pr
        memos["#{l}#{r}"] = [memo[1], pr]
        sum += memo[1]
      else
        memos["#{l}#{r}"] = [pr, memo[1]]
        sum += pr
      end
    else
      pl = ps[l - 1]
      if pl < pr
        memos["#{l}#{r}"] = [pl, pr]
        sum += pl
      elsif pr < pl
        memos["#{l}#{r}"] = [pr, pl]
        sum += pr
      else
        memos["#{l}#{r}"] = [pl, pr]
        sum += pl
      end
    end
  end
end

puts sum