// Traces the basic partitioning technique in Sedgewick

import java.util.Scanner;
import java.util.Random;

public class partition
{

  static ITEM[] arr;
  static int arrSize;

  static boolean less(ITEM x,ITEM y)
  {
    return x.less(y);
  }

  static void exch(ITEM[] a, int i, int j)
  {
    ITEM t = a[i];
    a[i] = a[j];
    a[j] = t;
  }

  static void dump(ITEM[] a,int i,int j)
  {
    int k;

    for (k=0;k<arrSize;k++)
    {
      if (k==i)
        System.out.print("A");
      else
        System.out.print(" ");
      if (k==j+1)
        System.out.print("B");
      else
        System.out.print(" ");
      System.out.format("%2d ",arr[k].getValue());
    }
    if (j==arrSize-1)
      System.out.print("B");
  }

  static int partition(ITEM a[], int l, int r)
  { 
    // From Sedgewick, but more complicated since pointers move
    // towards each other.
    // Elements before i are <= pivot.
    // Elements after j are >= pivot.
    int i = l-1, j = r; ITEM v = a[r];

    for (;;)
      {
        // Since pivot is the right end, this while has a sentinel.
        // Stops at any element >= pivot
        while (true)
        {
          ++i;
          dump(a,i,j);
          if (!less(a[i], v))
            break;
          System.out.print(" Left continues\n");
        }
        System.out.print(" Left positioned\n");
        // Stops at any element <= pivot (but not the pivot) or at the left end
        while (true)
        {
          --j;
          dump(a,i,j);
          if (!less(v,a[j]))
            break;
          if (j == l) break;
          System.out.print(" Right continues\n");
        }

        if (i >= j) break; // Don't need to swap
        System.out.print(" Right positioned\n");
        exch(a, i, j);
        dump(a,i,j);
        System.out.print(" After swap\n");
      }
    System.out.print(" Pointers collided\n");
    exch(a, i, r);     // Place pivot at final position for sort

    return i;
  }

  public static void main(String[] args)
  {
  int i;
  Random generator;

  Scanner sc=new Scanner(System.in);
  arrSize=sc.nextInt();
  arr=new ITEM[arrSize];

  for (i=0;i<arrSize;i++)
    arr[i]=new ITEM(sc.nextInt(),i);

  i=partition(arr,0,arrSize-1);
  for (int j=0;j<arrSize;j++)
    if (j==i)
      System.out.format(" <%2d>",arr[j].getValue());
    else
      System.out.format("  %2d ",arr[j].getValue());
  System.out.print(" Pivot positioned\n");
  }

}