class Mediane extends MacLib {
    static int J=300;


    public static void swap(int t[], int i, int j) {
        Rect r = new Rect();
        int p = t[i];
        t[i]=t[j];
        t[j]=p;
        //        foreColor(whiteColor);
        //setRect(r,i+4,4,i+5,J-4);
        //paintRect(r);
        //setRect(r,j+4,4,j+5,J-4);
        //paintRect(r);
        //setRect(r,i+4,J-t[i]+4,i+5,J-t[i]+5);
        //invertRect(r);
        //setRect(r,j+4,J-t[j]+4,j+5,J-t[j]+5);
        //invertRect(r);
    }

    public static void bbarre (int tab[], int i) {
        Rect r = new Rect();
        foreColor(blueColor);
        setRect(r,i+4,4,i+5,J-4);
        paintRect(r);
        foreColor(blackColor);
        //        try { Thread.sleep(500); }
        //        catch ( Exception e ) {}
    }

    public static void wbarre(int tab[], int i) {
        Rect r = new Rect();
        foreColor(whiteColor);
        setRect(r,i+4,4,i+5,J-4);
        paintRect(r);
        setRect(r,i+4,tab[i]+4,i+5,tab[i]+5);
        foreColor(blackColor);
        paintRect(r);
    }

    public static void affiche (int tab[], int g, int d) {
        Rect r = new Rect();
        setRect(r,4+g,4,d+5,J+4);
        foreColor(whiteColor);
        paintRect(r);
        foreColor(blackColor);
        for (int i=g; i<d; i++) {
            setRect(r,i+4,J-tab[i]+4,i+5,J-tab[i]+5);
            paintRect(r);
        }
    }
    public static int ran(int i, int j) {
        return((int)(i+(j-i)*Math.random()));
    }
    public static void hasard (int tab[], int d) {
        boolean[] tr = new boolean[d];
        int m,k;
        for (int j=0; j<d; j++)
            tr[j]=true;
        for (int j=0; j<d; j++) {
            k=ran(0,d-j);
            m=0;
            while (!tr[m]) m++;
            for (int l=1; l<k; l++) {
                m++;
                while (!tr[m]) m++;
            }
            tab[j]=m;
            tr[m]=false;
        }
    }



    public static int partition (int tab[], int g,int d) {
       int k=g+1; int l=d;
       while ( l+1!=k )  {
            if (tab[k]<tab[g])
                k++;
            else {
                swap(tab,k,l);
                l=l-1;
            }
        }
        if (k!=g+1) swap(tab,g,l);
        else l=g ;
        return (l);
    }

    public static int mediane (int tab[], int g, int d,int t) {
        int b;
        b = partition(tab,g,d);
        if (b==t) {
            affiche(tab,g,d);
            bbarre(tab, b);
            return(tab[b]);
        }
        else if (b<t) {
          try { Thread.sleep ( 1000 ) ; }
          catch ( Exception e ) {}
          affiche(tab,g+1,d-1);
          try { Thread.sleep ( 1000 ) ; }
          catch ( Exception e ) {}   
          affiche(tab,g,g);
          bbarre(tab,b+1);
          return(mediane(tab,b+1,d,t));
        }
        else {
           try { Thread.sleep ( 1000 ) ; }
          catch ( Exception e ) {}
          affiche ( tab, g+1, d-1 );
          try { Thread.sleep ( 1000 ) ; }
          catch ( Exception e ) {}
          affiche(tab,d,d);
          bbarre(tab,b-1);
          return(mediane(tab,g,b-1,t));
        }
    }

  public static void main (String argv[]) {
    int rang;
    if (argv.length==1) {
      rang=Integer.parseInt(argv[0]);
      InitQuickDraw();
      Rect r = new Rect(100,100,J+120,J+120);
      setDrawingRect(r);
      showDrawing();
      setRect(r,4,4,J+5,J+5);
      frameRect(r);
      setRect(r,5,5,J+4,J+4);
      int tab[] = new int[J];
      hasard(tab,J);
      affiche(tab,0,J);
      bbarre(tab,0);
      bbarre(tab,J-1);
      try { Thread.sleep(1000); }
      catch ( Exception e) { }
      int k = mediane(tab,0,J-1,(int)(rang));
      System.out.print(k);
    }
  }
}