program Sort;
var
i,j,n,k:longint;
a:array[1..100000] of longint;
b:array[1..1000,1..1000] of longint;
razmer:array[1..1000] of integer;
{с помощью QSort мы будем сортировать карманы}
procedure QSort(first,last:integer);
var
L,R,c,X:integer;
begin
if first < last then
begin
X:= b[i,(first + last) div 2];
L:= first;
R:= last;
while L <= R do
begin
while b[i,L] < X do
L:= L + 1;
while b[i,R] > X do
R:= R - 1;
if L <= R then
begin
c:=b[i,L];
b[i,L]:=b[i,R];
b[i,R]:=c;
L:=L+1;
R:=R-1;
end;
end;
QSort(first, R);
QSort(L, last);
end;
end;
{заполняем массив}
begin
read(n);
for i:=1 to n do
a[i]:=random(10000);
{выводим исходный массив}
for i:=1 to n do
write(a[i],' ');
{раббиваем массив на карманы}
for i:=1 to n do
begin
b[(a[i] div 10)+1,razmer[(a[i] div 10)+1]+1]:=a[i];
razmer[(a[i] div 10)+1]:=razmer[(a[i] div 10)+1]+1;
end;
{сортируем карманы}
for i:=1 to 1000 do
if razmer[i]<>0 then Qsort(1,razmer[i]);
{восстанавливаем массив}
k:=0;
for i:=1 to 1000 do
for j:=1 to razmer[i] do
begin
k:=k+1;
a[k]:=b[i,j];
end;
{выводим отсортированный массив}
writeln;
writeln;
for i:=1 to n do
write(a[i],' ');
end.