/* This is a preliminary version; it needs some optimization and improvemets */   

#include<stdio.h>
int n, q, v[20], p_v[20], 
          pi[20],pi_1[20],p_pi[20], 
	  delta[20], size_delta,
	  sigma[20], sigma_1[20], p_sigma[20],
	  w[20], p_w[20],
	  freq[20],
          cum_freq[20], freq_cum_w[20];

int check_dense()
{ int i, res=1;
  for(i=1;i<=q;i++)if ( freq[i]==0 ) return 0;
  return 1;
}

/* concerning s */
void fill_frequence()
{ int i;
  for(i=1;i<=q;i++)freq[i]=0;
  for(i=1;i<=n;i++)freq[v[i]]++;
}

void partition_s()
{ int i=1,j,k;
   p_v[1]=1;
   for(j=1;j<=q;j++)
   { p_v[i]=1; i++; for(k=1;k<=freq[j]-1;k++) { p_v[i]=0; i++;} }
}

/* concerning sigma */
void expand_s()
{ int i;
  cum_freq[1]=1;
  for(i=2;i<=q;i++) cum_freq[i]=cum_freq[i-1]+freq[i-1];
  for(i=1;i<=n;i++) { pi[i]= cum_freq[v[i]]; cum_freq[v[i]]++;}

}


void partition_pi()
{ int i; 
  for(i=1;i<=n;i++) pi_1[pi[i]]=i;
  p_pi[1]=1;
  for(i=2;i<=n;i++) if( pi_1[i]>pi_1[i-1] ) 
                    p_pi[i]=0;
		    else p_pi[i]=1;
}

/* concerning tau */

void alex_bij()
{ int i;
  sigma[1]=pi[1];
  for(i=2;i<=n;i++)
  if(pi[i]>pi[1])
  sigma[n-i+2]=n-(pi[i]-pi[1])+1;
  else sigma[n-i+2]=pi[1]-pi[i];
}

void partition_sigma()
{ int i; 
  for(i=1;i<=n;i++) sigma_1[sigma[i]]=i;
  p_sigma[1]=1;
  for(i=2;i<=n;i++) if( sigma_1[i]>sigma_1[i-1] ) 
                    p_sigma[i]=0;
		    else p_sigma[i]=1;
}

void comp_delta()
{ int i,j=0,k=0;
  for(i=1;i<=n;i++)
  if( p_pi[i]==0 )
  { k++;
    if(p_v[i]==1) 
    { j++;
      delta[j]=k;
    }
  }  
  size_delta=j;
   
}

/* concerning tau */

void partition_t()
{ int i,j=1,k=0;
  for(i=1;i<=n;i++) 
  if(p_sigma[i]==1) p_w[i]=1;
  else { k++;
         if(delta[j]==k) { p_w[i]=1;j++;}
	 else  p_w[i]=0;
	} 
}			   

void fill_frequence_t()
{ int i,k=1;
  freq_cum_w[0]=0;
  for(i=2;i<=n;i++)
   if(p_w[i]==1) { freq_cum_w[k]=i-1; k++;}
   freq_cum_w[k]=n;
}  

void fill_t()
{ int i,j;
  for(i=1;i<=n;i++)
  for(j=1;j<=q;j++)
  if(sigma[i]>freq_cum_w[j-1] && sigma[i]<=freq_cum_w[j])
  w[i]=j;
}  
 
int maj_s()
{ int i,res=0;
  for (i=1;i<=n-1;i++)
  if(v[i]>v[i+1])res+=i;
  return res;
}

int maj_t()
{ int i,res=0;
  for (i=1;i<=n-1;i++)
  if(w[i]>w[i+1])res+=i;
  return res;
}


int stat_s()
{ int i,j,res=0;
  for (i=1;i<=n-1;i++)
  if(v[i]>v[i+1])res++;
  
  for (i=1;i<=n-2;i++)
  { if(v[i]>v[i+1])for (j=i+2;j<=n;j++)
          if(v[j]>=v[i] )res++;
  
    if(v[i]>v[i+1])for (j=i+2;j<=n;j++)
          if(v[j]<v[i+1] )res++;
    
    if(v[i]<v[i+1])for (j=i+2;j<=n;j++)
          if(v[j]<v[i+1] && v[j]>=v[i])    res++;
  }
  return res;
} 

int stat_t()
{ int i,j,res=0;
  for (i=1;i<=n-1;i++)
  if(w[i]>w[i+1])res++;
  
  for (i=1;i<=n-2;i++)
  { if(w[i]>w[i+1])for (j=i+2;j<=n;j++)
          if(w[j]>=w[i] )res++;
  
    if(w[i]>w[i+1])for (j=i+2;j<=n;j++)
          if(w[j]<w[i+1] )res++;
    
    if(w[i]<w[i+1])for (j=i+2;j<=n;j++)
          if(w[j]<w[i+1] && w[j]>=w[i])    res++;
  }
  return res;
}   


main()
{ int i;
  printf("give the length n:"); scanf("%d",&n);
  printf("give the arity q:"); scanf("%d",&q);
  printf("give the words v using each letter in 1..q at least once\n"); 
  
  for(i=1;i<=n;i++)
  { printf("v[%d]",i); scanf("%d",&v[i]); }
  
  fill_frequence();
  if(check_dense() )
{
  partition_s(); printf("the partition of v: "); 
  
  for(i=1;i<=n;i++) if ( p_v[i]==1 )printf("|%d ",i); else printf("%d ",i);
  printf("\n");
  
  expand_s(); printf("pi=the expansion of v: "); 
  for(i=1;i<=n;i++)
  printf("%d ",pi[i]); 
  printf("\n");

  partition_pi(); printf("the partition of pi : "); 
  for(i=1;i<=n;i++) if (p_pi[i] ==1)printf("|%d ",i); else printf("%d ",i);
  printf("\n");
  
  
  alex_bij(); printf("sigma= the image of pi : ");
  for(i=1;i<=n;i++)
  printf("%d ",sigma[i]); 
  printf("\n");
  
  partition_sigma(); printf("the partition of sigma : "); 
  for(i=1;i<=n;i++)if ( p_sigma[i]==1)printf("|%d ",i); else printf("%d ",i);
  printf("\n");
  
  
  comp_delta();/* printf("delta : "); 
  for(i=1;i<=size_delta;i++)
  printf("%d ",delta[i]);
  printf("\n"); */
  
  partition_t(); printf("the partition of w : ");
  for(i=1;i<=n;i++)if ( p_w[i]==1)printf("|%d ",i); else printf("%d ",i);
  printf("\n"); 
  
  partition_t(); fill_frequence_t(); fill_t();
  printf("w : ");
  for(i=1;i<=n;i++)
  printf("%d ",w[i]);
  printf("\n");
  
  
  printf("************************\n");
  printf("v : "); for(i=1;i<=n;i++) printf("%d ",v[i]);
  printf("\n");
  
  printf("w : "); for(i=1;i<=n;i++) printf("%d ",w[i]);
  printf("\n");
  
  printf("maj v =%d; stat v =%d; ",maj_s(), stat_s());
  printf("\n");
  printf("maj w =%d; stat w =%d; ",maj_t(), stat_t());
  printf("\n");
}
}