N = int(eval(input()))

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

ma = sum(As)

o = dict()

INF = 10**19

from itertools import accumulate

aa = [0] + list(accumulate(As))



for i in range(N):

    for j in range(N-i):

        span = i*N+j

        # 長さi+1, 開始位置jの合成コスト+構成要素の和

        if i == 0:

            o[span] = As[j]

            continue

        C = INF

#        print(i,j,o)

        for k in range(i):

            # 長さk+1とi+1-(k+1)=i-kに分割

#            print(i,j,k*N+j, (i-k-1)*N+j+k, o)

            C = min(C, o[k*N+j]+o[(i-k-1)*N+j+k+1])

#        o[span] = C + sum(As[j:j+i+1])

        o[span] = C + aa[j+i+1] - aa[j]



print((o[span]-ma))

N = int(eval(input()))

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

o = [0]*(N**2)

INF = 10**19

from itertools import accumulate

aa = [0] + list(accumulate(As))



for i in range(1, N+1):

    for j in range(N-i+1):

        span = (i-1)*N+j

        # 長さi, 開始位置jの合成コスト+構成要素の和

        if i == 1:

            o[span] = As[j]

            continue

        C = INF

        for k in range(1, i):

            # 長さ,開始位置=(k,j)と(i-k,j+k)

            span1, span2 = (k-1)*N+j, (i-k-1)*N+j+k

            C = min(C, o[span1]+o[span2])

        o[span] = C + aa[(j+i-1)+1] - aa[(j-1)+1]

print((o[span]-aa[-1]))
N = int(eval(input()))
As = list(map(int, input().split()))
ma = sum(As)
o = dict()
INF = 10**19
from itertools import accumulate

aa = [0] + list(accumulate(As))
for i in range(N):
    for j in range(N - i):
        span = i * N + j
        # 長さi+1, 開始位置jの合成コスト+構成要素の和
        if i == 0:
            o[span] = As[j]
            continue
        C = INF
        #        print(i,j,o)
        for k in range(i):
            # 長さk+1とi+1-(k+1)=i-kに分割
            #            print(i,j,k*N+j, (i-k-1)*N+j+k, o)
            C = min(C, o[k * N + j] + o[(i - k - 1) * N + j + k + 1])
        #        o[span] = C + sum(As[j:j+i+1])
        o[span] = C + aa[j + i + 1] - aa[j]
print((o[span] - ma))

N = int(eval(input()))
As = list(map(int, input().split()))
o = [0] * (N**2)
INF = 10**19
from itertools import accumulate

aa = [0] + list(accumulate(As))
for i in range(1, N + 1):
    for j in range(N - i + 1):
        span = (i - 1) * N + j
        # 長さi, 開始位置jの合成コスト+構成要素の和
        if i == 1:
            o[span] = As[j]
            continue
        C = INF
        for k in range(1, i):
            # 長さ,開始位置=(k,j)と(i-k,j+k)
            span1, span2 = (k - 1) * N + j, (i - k - 1) * N + j + k
            C = min(C, o[span1] + o[span2])
        o[span] = C + aa[(j + i - 1) + 1] - aa[(j - 1) + 1]
print((o[span] - aa[-1]))

-ma = sum(As) -o = dict() +o = [0] * (N**2) -for i in range(N): -    for j in range(N - i): -        span = i * N + j -        # 長さi+1, 開始位置jの合成コスト+構成要素の和 -        if i == 0: +for i in range(1, N + 1): +    for j in range(N - i + 1): +        span = (i - 1) * N + j +        # 長さi, 開始位置jの合成コスト+構成要素の和 +        if i == 1: -        #        print(i,j,o) -        for k in range(i): -            # 長さk+1とi+1-(k+1)=i-kに分割 -            #            print(i,j,k*N+j, (i-k-1)*N+j+k, o) -            C = min(C, o[k * N + j] + o[(i - k - 1) * N + j + k + 1]) -        #        o[span] = C + sum(As[j:j+i+1]) -        o[span] = C + aa[j + i + 1] - aa[j] -print((o[span] - ma)) +        for k in range(1, i): +            # 長さ,開始位置=(k,j)と(i-k,j+k) +            span1, span2 = (k - 1) * N + j, (i - k - 1) * N + j + k +            C = min(C, o[span1] + o[span2]) +        o[span] = C + aa[(j + i - 1) + 1] - aa[(j - 1) + 1] +print((o[span] - aa[-1]))