program proj;

{$APPTYPE CONSOLE}

uses
  SysUtils,Windows;
type
  TDana = integer; // deklaracja jakiejś danej
  Drzewo = ^TDrzewo; // typ wskazujący na drzewko bo przecież musimy pamiętac jego potomków...
  TDrzewo = record   // drzewko
    licznik,stan,etykieta: TDana;  // to jest nasza dana, może być ich oczywiście więcej
    przodek,lewy,prawy: Drzewo;  // przodek,potomkowie
    wywaz: -1..1;
  end;

var
        timeEnd,TimeStart,freq,timestart1,timeend1:Int64;
                  czas:extended;
B,T:array[0..9000000] of Int64;
 Ba:array[0..9000000] of Int64;
korzen,m,elem,p,a,j,i,n,z,k,zakres:Longint;
dana: TDana;
drzewko: Drzewo;
wys:integer;


// procedura wstawiania  jednego elementu na liste
procedure  DrzewoAVL;
procedure Wstaw(var W : Drzewo; Co : TDana);
begin
  if W = nil then
  begin
    new(W);
    W^.lewy:=nil;
    W^.prawy:=nil;
    W^.etykieta:=Co;
  end
  else
  if W^.etykieta >= Co then
    Wstaw(W^.lewy,Co)
  else
  if W^.etykieta < Co then
    Wstaw(W^.prawy,Co);
end;


procedure Create(var node:Drzewo; l, r : integer);     //metoda polowienia
          var
            mid  : integer;

        begin
            mid:=(l+r) div 2;
            
           // Write(ba[mid],' ');
            //Writeln('end');
            Wstaw(node,ba[mid]);
            if (mid-1)>=l then Create(node^.lewy,  l,(mid-1));
            if (mid+1)<=r then Create(node^.prawy, (mid+1),r);
       end;


procedure drukuj(W : Drzewo);                     // wypisywanie drzewa
begin
  if W <> nil then
  begin
  drukuj(W^.Lewy); //
  //drukuj(W^.Prawy);
  Write(W^.Etykieta,' ');
  drukuj(W^.Prawy);

  end;
end;

  Procedure Wyszukiwanie(W : drzewo);  // wyszukiwanie elementu
  var
  x:int64;
    Begin
      if W <> nil then
        begin
        if elem = W^.etykieta then x:=1;
        if elem < W^.etykieta then  Wyszukiwanie(W^.lewy)
          else  Wyszukiwanie(W^.prawy);
        end;
    END;

    
{  procedure drukujdrzewo(w:drzewo;h:integer);

     var i:integer;
    begin
     if w <> nil then
     with w^ do
     begin
       drukujdrzewo(lewy,h+1);
       for i:=1 to h do write(' ');
       writeln(etykieta);
       drukujdrzewo(prawy,h+1);
     end;
    End;}


  procedure Wysokosc(w:drzewo; ile : integer);
     begin
         if (w<>nil) then
            begin
   //     Writeln(ile);
               Wysokosc(w^.lewy, ile+1);
               Wysokosc(w^.prawy, ile+1);
               if ile>wys then wys:=ile;

            end;

        end;

procedure quicksortS(start,stop:longint);
var
h,i,j,x:longint;
BEgin
i:=start;
j:=stop;
x:=ba[(start+stop)div 2];

repeat
while (ba[j]>x) do  j:=j-1;
 while (ba[i]<x) do  i:=i+1;
if (i<=j)
  then
	BEgin
    h:=ba[i];
    ba[i]:=ba[j];
    ba[j]:=h;
    j:=j-1;
    i:=i+1;
  End;

until (i>=j);


    if (start<j) then quicksortS(start, j);
    if (i<stop) then quicksortS(i, stop);
end;
  Procedure Przegladanie(W:Drzewo);
    Begin
      if W<>nil then
        BEgin
         Przegladanie(W^.lewy);
         Przegladanie(W^.Prawy);
         W^.etykieta:=W^.etykieta+1;
        End;

    End;

  Procedure Wstawianie( x:integer; w:Drzewo; h:boolean);
     var p1,p2:Drzewo;
      Begin
         
         writeln('new');
      BEgin
      if w=nil then
        BEgin
          new(w);
          h:=true;
          with w^ do
            begin
             etykieta:=x;
             licznik:=1;
             lewy:=nil;
             prawy:=nil;
             wywaz:=0;
            end
        end
        else //w<>nil       drzewo nie jest puste.
       if x<w^.etykieta then
        BEgin

         wstawianie(x,W^.lewy,h);
         if h then // urosła lewa galaz
         case W^.wywaz of
          1:  begin
               W^.wywaz:=0;
               h:=false;
              end;
          0:  W^.wywaz:=-1;
          -1: begin
               p1:=W^.lewy;
               if p1^.wywaz=-1 then
                begin // pojedyncza zamiana LL
                  w^.lewy:=p1^.prawy;
                  p1^.prawy:=W;
                  W^.wywaz:=0;
                  w:=p1;
                end
               else   // podwojna zamiana LP
               begin
                 p2:=p1^.prawy;
                 p1.prawy:=p2^.lewy;
                 p2^.lewy:=p1;
                 w^.lewy:=p2^.prawy;
                 p2^.prawy:=w;
                 if p2^.wywaz=-1 then w^.wywaz:=1
                  else w^.wywaz:=0;
                 if p2^.wywaz=1 then p1^.wywaz:=-1
                  else p1^.wywaz:=0;
                 w:=p2;
                End;
                 w^.wywaz:=0;
                 h:=false;
                end
              end
        ENd
        ELSE
         if x>w^.etykieta then
         begin ////

          wstawianie(x,w^.prawy,h);
          if h then //urosła prawa galaz
          case w^.wywaz of
          -1: begin
                w^.wywaz:=0;
                h:=false;
              end;
          0:  w^.wywaz:=1;
          1:  begin//
               p1:=w^.prawy;
               if p1^.wywaz=1 then
                begin //pojedyncza zamiana pp
                   w^.prawy:=p1^.lewy;
                   p1^.lewy:=w;
                   w^.wywaz:=0;
                   w:=p1;
                end
               else
                begin // podwojna zamiana PL
                  p2:=p1^.lewy;
                  p1^.lewy:=p2^.prawy;
                  p2^.prawy:=p1;
                  w^.prawy:=p2^.lewy;
                  p2^.lewy:=w;
                  if p2^.wywaz=1 then w^.wywaz:=-1
                    else w^.wywaz:=0;
                  if p2^.wywaz=-1 then p1^.wywaz:=1
                    else p1^.wywaz:=0;
                end;
                w^.wywaz:=0;
                h:=false;
              end//
            end
         end////
      else
        begin
         w^.licznik:=w^.licznik+1;
         h:=false;
        end;
   end;
     // drukuj(w);
   //Writeln(' ');
 END;  



// program glówny


BEGIN
m:=0;
Writeln('Podaj n');
 Readln(n);
 Writeln('podaj zakres');
 Readln(zakres);
//repeat

  for i:=0 to zakres do B[i]:=1;
  p:=random(zakres)+1;                // tworzenie tablicy losowo, bez powtarzajacych sie elementow
  T[0]:=p;
  B[p]:=0;

  a:=1;
  //Writeln(B[p]);
 if zakres>=n then
    BEgin
    // Writeln('begin');

    // Write(T[0],' ');
      Repeat
      k:=0;
      i:=a;
      j:=random(zakres);
      if B[j]=1 then
          Begin
            T[a]:=j;
            B[j]:=0;

          //Write('j ',j,'wartosc = ',B[j]);
           // Write(' ',T[a],' ');
            a:=a+1;
          end;

      until (a=(n));
    End
      Else Writeln('Zly Zakres');

  writeln;
  Writeln(n);
  readln;

  for i:=0 to n-1 do
    Begin
 //   Write(T[i],' ');
    Ba[i]:=T[i];
    end;
 //glowny program

   quicksortS(0,n-1);
      Writeln('posortowany');
       for i:=0 to n-1 do
        Begin
          Write(Ba[i],' ');
        end;
    //readln;

{  if QueryPerformanceFrequency(Freq) then
    QueryPerformanceCounter(TimeStart);
    create(drzewko,0,n-1);
    QueryPerformanceCounter(TimeEND);
    czas:=(TimeEND-Timestart)/Freq*1000;;
    Writeln('czas tworzenia ',czas,' ');}

    //drukuj(drzewko);
    //    wysokosc(drzewko,0);
     //   writeln('Wysokosc drzewa ',wys);
{for j:=0 to ( n div 10)-1 do
    begin
      elem:=Ba[random(n)];
     // Writeln('elem ',elem,' ');
      Wyszukiwanie(drzewko);}
   //  end;

    readln;

    for i:=0 to n-1 do
    BEgin
    Wstawianie(ba[i],drzewko,false);
    drukuj(drzewko);
    end;

       //writeln('Wysokosc drzewa ',wys);
   // Writeln('porzadek wsteczny');
     // przegladanie(drzewko);
//      drukuj(Drzewko);
//m:=m+1;
 //   n:=n+100000;
 //until m=10;
  Readln;
end;


BEgin
DrzewoAVL;

END.