def resolve():

    N = int(eval(input()))

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

    DP = [[2 ** 63 -1  for _ in range(N+1)] for _ in range(N)]

    SUM = [[0 for _ in range(N+1)] for _ in range(N+1)]



    SUM[0][0] = 0

    for i in range(N):

        for j in range(i,N):

            SUM[i][j+1] = SUM[i][j] + a[j]

            if i < j:

                SUM[i+1][j] = SUM[i][j] - a[i]



    for i in range(N):

        j = i+1

        DP[i][j] = 0



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

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

            j = i + w

            for k in range(i,j):

                DP[i][j] = min(DP[i][k]+DP[k][j]+SUM[i][j],DP[i][j])

    print((DP[0][N]))

resolve()
def resolve():

    N = int(eval(input()))

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

    DP = [[2 ** 63 -1  for _ in range(N+1)] for _ in range(N)]

    SUM = [[0 for _ in range(N+1)] for _ in range(N+1)]

    RANGE = [[0 for _ in range(N+1)] for _ in range(N+1)]



    SUM[0][0] = 0

    for i in range(N):

        for j in range(i,N):

            SUM[i][j+1] = SUM[i][j] + a[j]

            if i < j:

                SUM[i+1][j] = SUM[i][j] - a[i]



    for i in range(N):

        j = i+1

        DP[i][j] = 0

        RANGE[i][j] = i



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

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

            j = i + w

            for k in range(RANGE[i][j-1],RANGE[i+1][j]+1):

                s = DP[i][k]+DP[k][j]+SUM[i][j]

                if DP[i][j] > s:

                    DP[i][j] = s

                    RANGE[i][j] = k

    print((DP[0][N]))

resolve()
def resolve():
    N = int(eval(input()))
    a = list(map(int, input().split()))
    DP = [[2**63 - 1 for _ in range(N + 1)] for _ in range(N)]
    SUM = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    SUM[0][0] = 0
    for i in range(N):
        for j in range(i, N):
            SUM[i][j + 1] = SUM[i][j] + a[j]
            if i < j:
                SUM[i + 1][j] = SUM[i][j] - a[i]
    for i in range(N):
        j = i + 1
        DP[i][j] = 0
    for w in range(2, N + 1):
        for i in range(N + 1 - w):
            j = i + w
            for k in range(i, j):
                DP[i][j] = min(DP[i][k] + DP[k][j] + SUM[i][j], DP[i][j])
    print((DP[0][N]))


resolve()

def resolve():
    N = int(eval(input()))
    a = list(map(int, input().split()))
    DP = [[2**63 - 1 for _ in range(N + 1)] for _ in range(N)]
    SUM = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    RANGE = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    SUM[0][0] = 0
    for i in range(N):
        for j in range(i, N):
            SUM[i][j + 1] = SUM[i][j] + a[j]
            if i < j:
                SUM[i + 1][j] = SUM[i][j] - a[i]
    for i in range(N):
        j = i + 1
        DP[i][j] = 0
        RANGE[i][j] = i
    for w in range(2, N + 1):
        for i in range(N + 1 - w):
            j = i + w
            for k in range(RANGE[i][j - 1], RANGE[i + 1][j] + 1):
                s = DP[i][k] + DP[k][j] + SUM[i][j]
                if DP[i][j] > s:
                    DP[i][j] = s
                    RANGE[i][j] = k
    print((DP[0][N]))


resolve()

+    RANGE = [[0 for _ in range(N + 1)] for _ in range(N + 1)] +        RANGE[i][j] = i -            for k in range(i, j): -                DP[i][j] = min(DP[i][k] + DP[k][j] + SUM[i][j], DP[i][j]) +            for k in range(RANGE[i][j - 1], RANGE[i + 1][j] + 1): +                s = DP[i][k] + DP[k][j] + SUM[i][j] +                if DP[i][j] > s: +                    DP[i][j] = s +                    RANGE[i][j] = k