n = int(eval(input()))

a = list(map(int, input().split()))



#dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値

dp = [[float("inf")]*(n+1) for i in range(n+1)]

for i in range(n):

    dp[i][i] = 0



#cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和

cost = [0]*(n+1)

for i in range(n):

    cost[i+1] = cost[i] + a[i]



#メモ化再帰でdp[0][n]求める

def dfs(l, r, infnum):

    if dp[l][r] != infnum:

        return dp[l][r]

    elif (r - l) == 1:

        dp[l][r] = 0

        return dp[l][r]

    else:

        res = float("inf")

        for k in range(l + 1, r):

            #dp[l][k] + dp[k][r] + 合体に必要なコスト

            res = min(res, dfs(l, k, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l]))

        dp[l][r] = res

    return dp[l][r]



dfs(0, n, float("inf"))

print((dp[0][n]))
n = int(eval(input()))

a = list(map(int, input().split()))

ruiseki = [0] * (n+1)

for i in range(n):

    ruiseki[i+1] = ruiseki[i] + a[i]



dp = [[-1]*(n+1) for i in range(n+1)]



def solve(l, r):

    if dp[l][r] != -1:

        return dp[l][r]

    if r - l == 1:

        dp[l][r] = 0

        return dp[l][r]

    ans = 10**18

    for i in range(l+1, r):

        ans = min(ans, solve(l, i) + solve(i, r) + ruiseki[r] - ruiseki[l])

    dp[l][r] = ans

    return dp[l][r]



solve(0, n)

print((dp[0][n]))
n = int(eval(input()))
a = list(map(int, input().split()))
# dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値
dp = [[float("inf")] * (n + 1) for i in range(n + 1)]
for i in range(n):
    dp[i][i] = 0
# cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和
cost = [0] * (n + 1)
for i in range(n):
    cost[i + 1] = cost[i] + a[i]
# メモ化再帰でdp[0][n]求める
def dfs(l, r, infnum):
    if dp[l][r] != infnum:
        return dp[l][r]
    elif (r - l) == 1:
        dp[l][r] = 0
        return dp[l][r]
    else:
        res = float("inf")
        for k in range(l + 1, r):
            # dp[l][k] + dp[k][r] + 合体に必要なコスト
            res = min(res, dfs(l, k, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l]))
        dp[l][r] = res
    return dp[l][r]


dfs(0, n, float("inf"))
print((dp[0][n]))

n = int(eval(input()))
a = list(map(int, input().split()))
ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + a[i]
dp = [[-1] * (n + 1) for i in range(n + 1)]


def solve(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    if r - l == 1:
        dp[l][r] = 0
        return dp[l][r]
    ans = 10**18
    for i in range(l + 1, r):
        ans = min(ans, solve(l, i) + solve(i, r) + ruiseki[r] - ruiseki[l])
    dp[l][r] = ans
    return dp[l][r]


solve(0, n)
print((dp[0][n]))

-# dp[l][r] = [l, r)区間のスライムを合体するときのコストの最小値 -dp = [[float("inf")] * (n + 1) for i in range(n + 1)] +ruiseki = [0] * (n + 1) -    dp[i][i] = 0 -# cost[r]-cost[l] = [l, r)区間を合計したときのスライムの総和 -cost = [0] * (n + 1) -for i in range(n): -    cost[i + 1] = cost[i] + a[i] -# メモ化再帰でdp[0][n]求める -def dfs(l, r, infnum): -    if dp[l][r] != infnum: +    ruiseki[i + 1] = ruiseki[i] + a[i] +dp = [[-1] * (n + 1) for i in range(n + 1)] + + +def solve(l, r): +    if dp[l][r] != -1: -    elif (r - l) == 1: +    if r - l == 1: -    else: -        res = float("inf") -        for k in range(l + 1, r): -            # dp[l][k] + dp[k][r] + 合体に必要なコスト -            res = min(res, dfs(l, k, infnum) + dfs(k, r, infnum) + (cost[r] - cost[l])) -        dp[l][r] = res +    ans = 10**18 +    for i in range(l + 1, r): +        ans = min(ans, solve(l, i) + solve(i, r) + ruiseki[r] - ruiseki[l]) +    dp[l][r] = ans -dfs(0, n, float("inf")) +solve(0, n)