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])