// Optimal matrix multiplication order using dynamic programming
// Notes 7.C

#include <stdio.h>

int p[20];
int n;
int c[20][20];
int trace[20][20];

void tree(int left,int right,int indent)
{
int i;

if (left==right) // At a leaf in the optimal tree
{
  printf("%*s%d\n",3*indent,"",left);  // Indent and print the index of the matrix
  return;
}

tree(trace[left][right]+1,right,indent+1);   // Print the right subtree for c(left,right)
printf("%*s%d %d\n",3*indent,"",left,right); // Print the root
tree(left,trace[left][right],indent+1);      // Print the left subtree for c(left,right)
}

int main()
{
int i,j,k;
int work;

scanf("%d",&n);  // Get the number of matrices

for (i=0;i<=n;i++)
  scanf("%d",&p[i]);  // Get the dimensions

for (i=1;i<=n;i++)
  c[i][i]=trace[i][i]=0;  // Process base case

for (i=1;i<n;i++)       // The difference between leftmost and rightmost matrix indices
  for (j=1;j<=n-i;j++)  // Leftmost index
  {
    printf("Compute c[%d][%d]\n",j,j+i);
    c[j][j+i]=999999;   // Initialize as infinity, then improve

    // k is the last matrix index for the left subtree, k+1 is the first matrix index for the right subtree
    for (k=j;k<j+i;k++) 
    {
      work=c[j][k]+c[k+1][j+i]+p[j-1]*p[k]*p[j+i];
      printf("  k=%d gives cost %3d=c[%d][%d]+c[%d][%d]+p[%d]*p[%d]*p[%d]\n",
        k,work,j,k,k+1,j+i,j-1,k,j+i);
      if (c[j][j+i]>work) // Is work an improvement?
      {
        c[j][j+i]=work;
        trace[j][j+i]=k;
      }
    }
    printf("  c[%d][%d]==%d,trace[%d][%d]==%d\n",j,j+i,
      c[j][j+i],j,j+i,trace[j][j+i]);
  }

printf("   ");
for (i=1;i<=n;i++)
  printf("   %3d   ",i);
printf("\n");
for (i=1;i<=n;i++)
{
  printf("%2d ",i);
  for (j=1;j<=n;j++)
    if (i>j)
      printf(" ------- "); // c(i,j) is not a thing
    else
      printf(" %3d %3d ",c[i][j],trace[i][j]);
  printf("\n");

  printf("\n");
}

tree(1,n,0);  // Print the tree for the optimal strategy
}