// Provides trace of A & B borders for Quicksort partitioning as
// in CSE 2320 Notes 8.
#include <stdio.h>
#include <stdlib.h>

int partition(arr,p,r)
// From CLRS, 2nd ed.
int *arr,p,r;
{
int x,i,j,temp;
int k;

printf("AB");
for (i=p;i<=r;i++)
  printf("%2d   ",arr[i]);
printf("\n");

x=arr[r];
i=p-1;
for (j=p;j<r;j++)
{
  if (arr[j]<=x)
  {
    i++;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
  }
  for (k=p;k<=r;k++)
  {
    if (k==i+1)
      printf("A");  // Keys printed before A are no larger than pivot
    else
      printf(" ");
    if (k==j+1)
      printf("B");  // Keys printed after A, but before B are larger than pivot
    else
      printf(" ");
    printf("%2d ",arr[k]);
  }
  printf("\n");
}
// Swap pivot to final position
temp=arr[i+1];
arr[i+1]=arr[r];
arr[r]=temp;

for (j=p;j<=i;j++)
  printf("  %2d ",arr[j]);
printf(" <%2d > ",arr[i+1]);  // < pivot >
for (j=i+2;j<=r;j++)
  printf("%2d   ",arr[j]);
printf("\n");
return i+1;
}

int main()
{
int *a,n,seed;
int i,j,temp,q;

scanf("%d",&n);
a=(int*) malloc(n*sizeof(int));
if (!a)
{
  printf("malloc failed %d\n",__LINE__);
  exit(0);
}

for (i=0;i<n;i++)
  scanf("%d",&a[i]);

/*
scanf("%d %d",&n,&seed);
srandom(seed);
for (i=0;i<n;i++)
  a[i]=i;
for (i=0;i<n-1;i++)
{
  j=i+abs(random())%(n-i);
  temp=a[j];
  a[j]=a[i];
  a[i]=temp;
}
*/

q=partition(a,0,n-1);
}