from time import clock
import sys

def Mult(i, j,matrix,ansseq):
     
     global ans     
     if (i==j):
          ans+=str(i)          
     else:
          k = ansseq[i][j]
          ans+=str("(")          
          Mult(i, k,matrix,ansseq)          
          Mult(k+1, j,matrix,ansseq)
          ans+=str(")")
         


def Matrix_multi():

     try:
          
          InFile=open('in_sec17_1.txt','r')
          OutFile=open('out_11_sec17_1.txt','w') 
          
          start=clock()
          
          InFile.readline()
          matrix=[]
          for num in InFile.readlines():
             matrix.append(int(num))               
          
## START
          
          ansseq=[[0 for col in range(len(matrix))] for row in range(len(matrix))]
          multi=[[0 for col in range(len(matrix))] for row in range(len(matrix))]
          
          for L in range(2,len(matrix)):
               for i in range(1,len(matrix)-L+1):
                    j=i+L-1
                    multi[i][j]=10000   ## as infinity
                    for k in range(i,j):
                         
                         mulcost = multi[i][k] + multi[k+1][j] + (matrix[i-1] * matrix[k] * matrix[j])
                         if (mulcost < multi[i][j]) : 
                              multi[i][j] = mulcost
                              ansseq[i][j] = k          
          
          OutFile.write("No of Multiplications are : "+str(multi[1][len(matrix)-1]))
          Mult(1,len(matrix)-1,matrix[1:len(matrix)],ansseq)
          OutFile.write("\nMultiplication Sequence is : "+str(ans))                    
## END           
          
          OutFile.write("\nTotal Excution Time : "+str(clock()-start))                    
          
          memUsed = sys.getsizeof(InFile) + sys.getsizeof(OutFile)+ sys.getsizeof(start)+ sys.getsizeof(matrix)+ sys.getsizeof(multi)+ sys.getsizeof(mulcost)
          OutFile.write("\nMemory used : "+str(memUsed)+" Bytes")        

          InFile.close()
          OutFile.close()
          
          print "Check Your Output File : out_11_sec17_1.txt is Generated"

     except ValueError:

          print "Check Your Output File Cant Not Generated",ValueError
          InFile.close()
          OutFile.close()


ans=""
Matrix_multi()