# 1. 输入示例
n = int(input().strip())

nums = [0]
nums.extend(list(map(int, input().split())))

s = [0]
for i in range(1, n+1):
    s.append(s[-1]+nums[i])

# 2. 初始化dp数组
dp = [[0 for i in range(n+1)] for j in range(n+1)]

for length in range(2, n+1):    # 遍历区间可能的长度
    for i in range(1, n+1-length+1):    # ！！！出错：在长度一定下，遍历可能的起点，需要满足 i+length-1<=n，边界条件是i=1，length=n时，边界应该小于等于n
        l = i
        r = i + length - 1

        dp[l][r] = float("inf")
        for k in range(l, r):    # ！！！出错：这里k可以取到左边界l，此时表示为dp[1][1] + dp[2][r],即分隔将第一堆和其他堆分开；但是k不可以取到右边界r，此时表示为dp[1][r] + dp[r+1][r],而当r=n时，n+1超出了索引范围
#             print(l,r,k) l=1;r = 5,k =5
            # 3. 状态转移方程
            dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+s[r]-s[l-1])    # s[r]-s[l-1]:表示最后两队合并的cost
print(dp[1][n])