import sys,queue,math,copy,itertools,bisect,collections,heapq

INF = 10**18

LI = lambda : [int(x) for x in sys.stdin.readline().split()]

NI = lambda : int(sys.stdin.readline())



N = NI()

a = LI()

sn = [[0 for _ in range(N)] for _ in range(N)]

dp = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N):

    x = 0

    for j in range(i,N):

        x += a[j]

        sn[i][j] = x

for i in range(N):

    dp[i][i] = 0

    if i < N-1:

        dp[i][i+1] = sn[i][i+1]



for j in range(2,N):

    for i in range(j-2,-1,-1):

        for k in range(0,j-i):

            dp[i][j] = min(dp[i][j],dp[i+k+1][j]+ dp[i][i+k] + sn[i][j])

print((dp[0][-1]))

import sys

INF = 10**14

LI = lambda : [int(x) for x in sys.stdin.readline().split()]

NI = lambda : int(sys.stdin.readline())



N = NI()

a = LI()

sn = [[0 for _ in range(N)] for _ in range(N)]

dp = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N):

    x = 0

    for j in range(i,N):

        x += a[j]

        sn[i][j] = x

for i in range(N):

    dp[i][i] = 0



for j in range(1,N):

    for i in range(j-1,-1,-1):

        for k in range(0,j-i):

            dp[i][j] = min(dp[i][j],dp[i+k+1][j]+ dp[i][i+k] + sn[i][j])

print((dp[0][-1]))
import sys, queue, math, copy, itertools, bisect, collections, heapq

INF = 10**18
LI = lambda: [int(x) for x in sys.stdin.readline().split()]
NI = lambda: int(sys.stdin.readline())
N = NI()
a = LI()
sn = [[0 for _ in range(N)] for _ in range(N)]
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    x = 0
    for j in range(i, N):
        x += a[j]
        sn[i][j] = x
for i in range(N):
    dp[i][i] = 0
    if i < N - 1:
        dp[i][i + 1] = sn[i][i + 1]
for j in range(2, N):
    for i in range(j - 2, -1, -1):
        for k in range(0, j - i):
            dp[i][j] = min(dp[i][j], dp[i + k + 1][j] + dp[i][i + k] + sn[i][j])
print((dp[0][-1]))

import sys

INF = 10**14
LI = lambda: [int(x) for x in sys.stdin.readline().split()]
NI = lambda: int(sys.stdin.readline())
N = NI()
a = LI()
sn = [[0 for _ in range(N)] for _ in range(N)]
dp = [[INF for _ in range(N)] for _ in range(N)]
for i in range(N):
    x = 0
    for j in range(i, N):
        x += a[j]
        sn[i][j] = x
for i in range(N):
    dp[i][i] = 0
for j in range(1, N):
    for i in range(j - 1, -1, -1):
        for k in range(0, j - i):
            dp[i][j] = min(dp[i][j], dp[i + k + 1][j] + dp[i][i + k] + sn[i][j])
print((dp[0][-1]))

-import sys, queue, math, copy, itertools, bisect, collections, heapq +import sys -INF = 10**18 +INF = 10**14 -    if i < N - 1: -        dp[i][i + 1] = sn[i][i + 1] -for j in range(2, N): -    for i in range(j - 2, -1, -1): +for j in range(1, N): +    for i in range(j - 1, -1, -1):