def qSort! (a,from,to)
 if from >= to then return(a) end;
 m = from;
 for i in from+1..to
   if a[i] < a[from]
     then m = m+1;
          swap(a,m,i);
   end
 end
 swap(a,from,m);
 qSort!(a,from,m-1);
 qSort!(a,m+1,to);
 return(a);
end; 

def swap(a,i,j)
 h = a[i];
 a[i] = a[j];
 a[j] = h
end;

#a = [5,1,7,3,6,9,2,4,8];
#qSort!(a,0,a.size-1);
#p(a);

a = IO.read("size_50000_1000000.array").to_a;

#a = Array.new(n);

for i in 0..a.size-1
 a[i]=a[i].to_i
 #a[i] = i;
end;

qSort!(a,0,a.size-1);
p(a[0,100]);