#include <stdio.h>
#include <malloc.h>

/* stack functions */
struct stack{
  int *s;
  int top;
};

struct stack* init(int n){
  struct stack *st;
  st = (struct stack *)malloc(sizeof(struct stack));
  st->s = (int *)malloc(n*sizeof(int));
  st->top = -1;
  return st;
}

void push(struct stack *st, int w){
  (st->top)+=1;
  st->s[st->top] = w;
}

int isempty(struct stack *st){
  if (st->top == -1)
    return 1;
  return 0;
}

int pop(struct stack *st){
  (st->top)--;
  return st->s[(st->top)+1];
}
/* end of stack functions */

int algo1(int T[], int n){
  int j;
  int x,y,z;
  int i_x,i_y,i_z;
  for(x=1; x<=n-2; x++){
    for(y=x+1; y<=n-1; y++){
      for(z=y+1; z<=n; z++){
	for(j=0; j<n; j++){
	  if(T[j] == x)
	    i_x = j;
	  if(T[j] == y)
	    i_y = j;
	  if(T[j] == z)
	    i_z = j;
	}
	if((i_x < i_z)&&(i_z < i_y))
	  return 0;
      }
    }
  }
  return 1;
}

int algo2(int T[], int n){
  int i,j,k;
  for(i=0; i<n-2; i++){
    for(j=i+1; j<n-1; j++){
      for(k=j+1; k<n; k++){
	if((T[i] < T[k])&&(T[k] < T[j]))
	  return 0;
      }
    }
  }
  return 1;
}

int algo3(int T[], int n){
  int i,j,p = -1;
  for(i=0; i<n-1; i++){
    p = -1;
    for(j=i+1; j<n; j++){
      if(T[j] > T[i] && p == -1)
	p=T[j];
      if(T[j] > T[i] && T[j] < p)
	return 0;
    }
  }
  return 1;
}

int algo4(int T[], int n){
  struct stack *st;
  st = init(n);
  int i, m = n;
  for (i=0; i<n; i++){
    while(T[i] <= m){
      push(st,m);
      m = m-1;
    }
    if(isempty(st))
      return 0;
    if(st->s[st->top] != T[i])
      return 0;
    pop(st);
  }
  return 1;
}


int main(){
  int *T, n, i;
  printf("\nn = ");
  scanf("%d", &n);
  printf("\nSequence: ");
  T = (int*)malloc(n*sizeof(int));
  for(i=0; i<n; i++){
    scanf("%d", &T[i]);
  }
  char *mus = "Musical", *unmus = "Unmusical";
  printf("\nAlgo 1: %s\n", (algo1(T,n) == 1)?mus:unmus);
  printf("\nAlgo 2: %s\n", (algo2(T,n) == 1)?mus:unmus);
  printf("\nAlgo 3: %s\n", (algo3(T,n) == 1)?mus:unmus);
  printf("\nAlgo 4: %s\n\n", (algo4(T,n) == 1)?mus:unmus);
  return 0;
}