#n=[10,20,30,7,40,3,61,4,5]
#n=[3,20,4]
#n=[2,100,4,90]
n=[100,4,90,2]
#n=[5,4,6,2,7]
#n=[10,100,5,50,1]
#n=[100,10,110,12,120]
#n=[10,110,15,50,1]
#n=[40,20,30,72,30,70,2,95,45,30,26,7,87]
#n=[3,28,4,21,5,2,6,21,7,24,3]
s=[[0 for i in range(len(n)-1)] for i in range(len(n)-1)]
def matProd(p):
  global s
  MAX=1000000000
  n=len(p)-1
  m1=[]
  m=[]
  for i in range(n):
    m1=m1+[MAX]
  for i in range(n):
    if (i<n-1):
      m=m+[m1[:i]+[0]+[p[i]*p[i+1]*p[i+2]]+m1[i+2:]]
    else:
      m=m+[m1[:i]+[0]]
  print (m)
  print (s)
  for L in range(2,n):
    for i in range(0,n-L):
      j=i+L
      for k in range(i,j):
#        print('i=',i)
#        print('k=',k)
#        print('j=',j)
        new=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1]
        print(new)
        if (new<m[i][j]):
          m[i][j]=new
          s[i][j]=k
  return m
print(matProd(n)) 
print(s)