const
   MAX = 30000;
var
   A: array[1..MAX] of integer;
   N: integer;

procedure Napln;
var  i: integer;
begin
   for i:=1 to N do
      A[i] := random( maxint )
end;

procedure Buble;
var i,j: integer;
    pom: integer;
begin
   for j:=1 to N-1 do
   for i:=1 to N-1 do
      if A[i] > A[i+1] then
      begin
         pom := A[i]; A[i] := A[i+1]; A[i+1] := pom
      end
end;



procedure VytvorHaldu( zac, kon: integer );
var i,j: integer;
    x: integer;
begin
   i := zac;
   j := 2*i;
   x := A[i];

   while j <= kon do
   begin
      if (j+1 <= kon) and (A[j+1] > A[j]) then
                                            j := j+1;
      if x >= A[j] then break
                   else
      begin
         A[i] := A[j];
         i := j;
         j := 2*i;
      end
   end;
   A[i] := x;
end;

procedure PostavHaldu;
var i: integer;
begin
   for i:=N div 2 downto 1 do
      VytvorHaldu( i, N )
end;

procedure Halda;
var i: integer;
    x: integer;
begin
   PostavHaldu;

   for i:=N downto 1 do
   begin
      x := A[ 1 ];
      A[ 1 ] := A[ i ];
      A[ i ] := x;
      VytvorHaldu( 1, i-1 )
   end
end;

procedure QS( zac,kon: integer );
var x,y: integer;
    pom, M: integer;
begin

   x := zac;  y := kon;
   M := (longint(A[zac])+A[kon]) div 2;
   repeat
      while A[x] < M do Inc(x);
      while A[y] > M do Dec(y);

      if x<=y then
      begin
         pom := A[x]; A[x] := A[y]; A[y] := pom;
         Inc( x ); Dec( y )
      end
   until x > y;
   if zac < y then QS(zac,y);
   if x < kon then QS(x,kon)
end;



var  i: integer;
begin
   for i:=1 to 16 do
   begin
      N := 1000*i;
      Napln;
      { Buble;{}
      { Halda; {}
      QS(1,N); {}
      writeln( N )
   end
end.