import java.io.*;

class Baum
{ 
    int wert;
    Baum l,r;

Baum(int x) { wert=x; }

static Baum einfügen(Baum b, int x) throws DuplicateElementException
{   if (b==null) return new Baum(x);
    for (Baum c = b;;) { 
       if (x<c.wert)      { if (c.l != null) c=c.l;
                            else {c.l = new Baum(x); break; }
                          }
       else if (x>c.wert) { if (c.r != null) c=c.r;
                            else {c.r = new Baum(x); break; }
                          }
       else throw new DuplicateElementException();
    }                   
    return b;
}  

static Baum löschen(Baum b, int x)
{   if (b==null) return b;
    if (b.wert == x) return löscheWurzel(b);
    for (Baum c = b;;) { 
       if (x<c.wert) { if (c.l == null) break;
                       if (c.l.wert == x) {c.l = löscheWurzel(c.l); break;}
                       else c=c.l;
                     }
       else          { if (c.r == null) break;
                       if (c.r.wert == x) {c.r = löscheWurzel(c.r); break;}
                       else c=c.r;
                     }
    }                   
    return b;
}  

private static Baum löscheWurzel(Baum b) // löscht die Wurzel des Baumes
{   if (b.l==null) return b.r;
    if (b.r==null) return b.l;
    Baum  c=b.r, cMutter=c;
    while (c.l != null) {cMutter=c; c=c.l;}
    if (c != cMutter) {
       cMutter.l = c.r;
       c.r = b.r;
    }
    c.l = b.l;
    return c;
}

//
//     DER REST IST ZUM TESTEN
//
//==================================================================
// Allgemeine Methode zum Durchlaufen in symmetrischer Reihenfolge
//
static void durchlaufe(Baum b, oper t)
{if (b==null) return;
 durchlaufe(b.l, t);
 t.bearbeite(b.wert);
 durchlaufe(b.r, t);
} 

static int[] a, aSort;
static int index;

private interface oper
{  void bearbeite(int i); }
private class drucken implements oper
{  public void bearbeite(int i) {System.out.print(i+" ");} }
private class vergleichen implements oper
{  public void bearbeite(int i)
  {if (i!=aSort[index++]) {
      System.out.println("Fehler "+i+" "+index+" "+aSort[i]);
      System.exit(1);
   }
} }

 
public static void main (String[] args) throws IOException
{// TESTPROGRAMM
    System.out.println("Sortieren mit einem Baum (treesort).");
    Baum b0 = new Baum(0);
    // Einlesen
      IntReader input = new IntReader(args);
      int länge = input.readInt();
        
    // Inititalisieren array und Sortieren:
      a = new int [länge];
      int ii = 0;
      Baum b = null;
      for (int i=0; i<länge; i++,ii++) {
         a[ii] = input.readInt();
         try {
             b = Baum.einfügen(b,a[ii]);
         }
         catch (DuplicateElementException e) { ii--; }
      }
      länge = ii;
      
    // Ausdrucken:
      durchlaufe(b, b0.new drucken());
      System.out.println(); 
      
    // Überprüfen:
      aSort = (int[]) a.clone(); java.util.Arrays.sort(aSort,0,länge);
      oper vergl = b0.new vergleichen();
      index = 0;
      durchlaufe(b, vergl);
      
      for (int i=0; i<länge; i++) {
    // ein Element wird jeweils gelöscht
          b = löschen(b,a[i]);
         // Überprüfen:
          aSort = (int[]) a.clone();
          java.util.Arrays.sort(aSort,i+1,länge);
          index = i+1;
          durchlaufe(b, vergl);
          System.out.print("l="+(länge-i-1)+" OK. ");
      }     
      System.out.println(); 
}

}

class DuplicateElementException extends Exception {}