from numpy import*

n,a=open(0)

n=int(n)

a=cumsum(int64([0]+a.split()))

dp=zeros((n,n+1),'i8')

for k in range(1,n):

  l=arange(n-k)

  r=arange(k+1,n+1)

  m=array([arange(i+1,i+k+1)for i in range(n-k)]).T

  dp[l,r]=amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]

print((dp[0,n]))
from numpy import*

n,a=open(0)

n=int(n)

a=cumsum(int64([0]+a.split()))

dp=zeros((n,n+1),'i8')

for k in range(1,n):

  l=arange(n-k)

  r=arange(k+1,n+1)

  m=(arange(1,k+1)+l[:,newaxis]).T

  dp[l,r]=amin(dp[l,m]+dp[m,r],0)+a[r]-a[l]

print((dp[0,n]))
from numpy import *

n, a = open(0)
n = int(n)
a = cumsum(int64([0] + a.split()))
dp = zeros((n, n + 1), "i8")
for k in range(1, n):
    l = arange(n - k)
    r = arange(k + 1, n + 1)
    m = array([arange(i + 1, i + k + 1) for i in range(n - k)]).T
    dp[l, r] = amin(dp[l, m] + dp[m, r], 0) + a[r] - a[l]
print((dp[0, n]))

from numpy import *

n, a = open(0)
n = int(n)
a = cumsum(int64([0] + a.split()))
dp = zeros((n, n + 1), "i8")
for k in range(1, n):
    l = arange(n - k)
    r = arange(k + 1, n + 1)
    m = (arange(1, k + 1) + l[:, newaxis]).T
    dp[l, r] = amin(dp[l, m] + dp[m, r], 0) + a[r] - a[l]
print((dp[0, n]))

-    m = array([arange(i + 1, i + k + 1) for i in range(n - k)]).T +    m = (arange(1, k + 1) + l[:, newaxis]).T