import sys

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 7)



import numpy as np



"""

最後の2つを決める：[0,x) [x,N)

小問題2つに分割できる。

全ての連続区間を計算すればよい

"""



N = int(eval(input()))

A = np.array(input().split(), np.int64)



# Acum[L,R] = A[L:R].sum()

Acum = np.zeros((N,N+1), dtype=np.int64)

for L in range(N):

    Acum[L,L+1:] = A[L:].cumsum()



dp = np.zeros((N,N+1), dtype=np.int64)

for size in range(2,N+1):

    for L in range(N-size+1):

        R = L + size

        dp[L,R] = (dp[L,L+1:R] + dp[L+1:R,R]).min() + Acum[L,R]



answer = dp[0,N]

print(answer)
import sys

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



import numpy as np



N = int(readline())

A = np.array(read().split(),np.int64)



INF = 10**18



# 左端ごとに、個数 -> 大きさ

size = np.full((N,N),INF,np.int64)

for n in range(N):

    size[n,:N-n] = A[n:].cumsum()



dpl = np.zeros((N,N),np.int64)

dpr = np.zeros((N,N),np.int64)



for n in range(1,N):

    x = np.min(dpl[:N-n,:n] + dpr[n:N,:n][:,::-1],axis=1)

    x += size[:N-n,n]

    dpl[:N-n,n] = x

    dpr[n:N,n] = x



answer = dpl[0,-1]

print(answer)
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import numpy as np

"""
最後の2つを決める：[0,x) [x,N)
小問題2つに分割できる。
全ての連続区間を計算すればよい
"""
N = int(eval(input()))
A = np.array(input().split(), np.int64)
# Acum[L,R] = A[L:R].sum()
Acum = np.zeros((N, N + 1), dtype=np.int64)
for L in range(N):
    Acum[L, L + 1 :] = A[L:].cumsum()
dp = np.zeros((N, N + 1), dtype=np.int64)
for size in range(2, N + 1):
    for L in range(N - size + 1):
        R = L + size
        dp[L, R] = (dp[L, L + 1 : R] + dp[L + 1 : R, R]).min() + Acum[L, R]
answer = dp[0, N]
print(answer)

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

N = int(readline())
A = np.array(read().split(), np.int64)
INF = 10**18
# 左端ごとに、個数 -> 大きさ
size = np.full((N, N), INF, np.int64)
for n in range(N):
    size[n, : N - n] = A[n:].cumsum()
dpl = np.zeros((N, N), np.int64)
dpr = np.zeros((N, N), np.int64)
for n in range(1, N):
    x = np.min(dpl[: N - n, :n] + dpr[n:N, :n][:, ::-1], axis=1)
    x += size[: N - n, n]
    dpl[: N - n, n] = x
    dpr[n:N, n] = x
answer = dpl[0, -1]
print(answer)

-input = sys.stdin.readline -sys.setrecursionlimit(10**7) +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +readlines = sys.stdin.buffer.readlines -""" -最後の2つを決める：[0,x) [x,N) -小問題2つに分割できる。 -全ての連続区間を計算すればよい -""" -N = int(eval(input())) -A = np.array(input().split(), np.int64) -# Acum[L,R] = A[L:R].sum() -Acum = np.zeros((N, N + 1), dtype=np.int64) -for L in range(N): -    Acum[L, L + 1 :] = A[L:].cumsum() -dp = np.zeros((N, N + 1), dtype=np.int64) -for size in range(2, N + 1): -    for L in range(N - size + 1): -        R = L + size -        dp[L, R] = (dp[L, L + 1 : R] + dp[L + 1 : R, R]).min() + Acum[L, R] -answer = dp[0, N] +N = int(readline()) +A = np.array(read().split(), np.int64) +INF = 10**18 +# 左端ごとに、個数 -> 大きさ +size = np.full((N, N), INF, np.int64) +for n in range(N): +    size[n, : N - n] = A[n:].cumsum() +dpl = np.zeros((N, N), np.int64) +dpr = np.zeros((N, N), np.int64) +for n in range(1, N): +    x = np.min(dpl[: N - n, :n] + dpr[n:N, :n][:, ::-1], axis=1) +    x += size[: N - n, n] +    dpl[: N - n, n] = x +    dpr[n:N, n] = x +answer = dpl[0, -1]