if __name__ == "__main__":  # 读取第一行的n  n = int(sys.stdin.readline().strip())
    line = sys.stdin.readline().strip()
    values = list(map(int, line.split()))
    ans = [[0 for i in range(n)] for j in range(n)] for i in range(1,n+1):  for j in range(n-i+1):  if i==1:  ans[j][j+i-1]=values[j] continue  else:  if values[j]==values[j+i-1]:  if i>2:  ans[j][j+i-1] = 2*values[j] + ans[j+1][j+i-2] else:  ans[j][j + i - 1] = 2 * values[j] else:  ans[j][j + i - 1] = min(2*values[j]+ans[j+1][j+i-1], 2*values[j+i-1]+ans[j][j+i-2]) print(ans[0][n-1])