区间dp TLE

n=int(input())
a=list(map(int,input().split()))
s=[1 for i in range(n+1)]
for i in range(1,n+1):
    s[i]=a[i-1]+s[i-1]

f=[[0 for i in range(n+1)] for j in range(n+1)]

for len in range(1,n):
    i=1
    while(i+len<=n):
        j=i+len
        f[i][j]=float('inf')
        for k in range(i,j):
            f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+(s[k]-s[i-1])*(s[j]-s[k]))
        i+=1

print(f[1][n])