$n = gets.to_i
$a = [0] + (1..$n-1).map{ gets.to_i }
$upper_bound = Float::INFINITY
$memo = Hash.new

def f(lesser, greater, i, consumed)
	if cache = $memo[[lesser, greater, i]]
		return cache + consumed
	end
	return consumed if lesser + $n - i == greater
	return Float::INFINITY if lesser + $n - i < greater
	return Float::INFINITY if consumed >= $upper_bound
	
	min = Float::INFINITY
	($n-1).downto(i+1).each{|j|
		a, b = lesser+j-i, greater
		m = nil
		m = (a < b ? f(a, b, j, consumed + $a[j]) : f(b, a, j, consumed + $a[j]))
		min = m if m < min
	}
	if min < $upper_bound
		$upper_bound = min
	end
	
	$memo[[lesser, greater, i]] = min - consumed
	min
end

p f(0, 0, 0, 0)