#include<bits/stdc++.h>
using namespace std;
const int xx=1e6+5;
unsigned A[xx],b[xx];
int cnt0[1<<8],cnt8[1<<8],cnt16[1<<8],cnt24[1<<8];
int n;unsigned seed;
inline void init_dAtA(){
memset(cnt0,0,sizeof(cnt0));
memset(cnt8,0,sizeof(cnt8));
memset(cnt16,0,sizeof(cnt16));
memset(cnt24,0,sizeof(cnt24));
for(unsigned *to=A+n,*now=A;now<to;++now){
seed=*now;
++cnt0[seed&255];
++cnt8[seed>>8&255];
++cnt16[seed>>16&255];
++cnt24[seed>>24&255];
}
}
inline void Sort(){
for(int i=1;i<256;++i){
cnt0[i]+=cnt0[i-1];
cnt8[i]+=cnt8[i-1];
cnt16[i]+=cnt16[i-1];
cnt24[i]+=cnt24[i-1];
}
int rep=n>>3,tim=rep;
unsigned *now=A+n-1;
while(tim--){
b[--cnt0[now[0]&255]]=now[0];
b[--cnt0[now[-1]&255]]=now[-1];
b[--cnt0[now[-2]&255]]=now[-2];
b[--cnt0[now[-3]&255]]=now[-3];
b[--cnt0[now[-4]&255]]=now[-4];
b[--cnt0[now[-5]&255]]=now[-5];
b[--cnt0[now[-6]&255]]=now[-6];
b[--cnt0[now[-7]&255]]=now[-7];now-=8;
}
switch(n&7){
case 7:{b[--cnt0[*now&255]]=*now;--now;}
case 6:{b[--cnt0[*now&255]]=*now;--now;}
case 5:{b[--cnt0[*now&255]]=*now;--now;}
case 4:{b[--cnt0[*now&255]]=*now;--now;}
case 3:{b[--cnt0[*now&255]]=*now;--now;}
case 2:{b[--cnt0[*now&255]]=*now;--now;}
case 1:{b[--cnt0[*now&255]]=*now;--now;}
}
tim=rep;
now=b+n-1;
while(tim--){
A[--cnt8[now[0]>>8&255]]=now[0];
A[--cnt8[now[-1]>>8&255]]=now[-1];
A[--cnt8[now[-2]>>8&255]]=now[-2];
A[--cnt8[now[-3]>>8&255]]=now[-3];
A[--cnt8[now[-4]>>8&255]]=now[-4];
A[--cnt8[now[-5]>>8&255]]=now[-5];
A[--cnt8[now[-6]>>8&255]]=now[-6];
A[--cnt8[now[-7]>>8&255]]=now[-7];now-=8;
}
switch(n&7){
case 7:{A[--cnt8[*now>>8&255]]=*now;--now;}
case 6:{A[--cnt8[*now>>8&255]]=*now;--now;}
case 5:{A[--cnt8[*now>>8&255]]=*now;--now;}
case 4:{A[--cnt8[*now>>8&255]]=*now;--now;}
case 3:{A[--cnt8[*now>>8&255]]=*now;--now;}
case 2:{A[--cnt8[*now>>8&255]]=*now;--now;}
case 1:{A[--cnt8[*now>>8&255]]=*now;--now;}
}
tim=rep;
now=A+n-1;
while(tim--){
b[--cnt16[now[0]>>16&255]]=now[0];
b[--cnt16[now[-1]>>16&255]]=now[-1];
b[--cnt16[now[-2]>>16&255]]=now[-2];
b[--cnt16[now[-3]>>16&255]]=now[-3];
b[--cnt16[now[-4]>>16&255]]=now[-4];
b[--cnt16[now[-5]>>16&255]]=now[-5];
b[--cnt16[now[-6]>>16&255]]=now[-6];
b[--cnt16[now[-7]>>16&255]]=now[-7];now-=8;
}
switch(n&7){
case 7:{b[--cnt16[*now>>16&255]]=*now;--now;}
case 6:{b[--cnt16[*now>>16&255]]=*now;--now;}
case 5:{b[--cnt16[*now>>16&255]]=*now;--now;}
case 4:{b[--cnt16[*now>>16&255]]=*now;--now;}
case 3:{b[--cnt16[*now>>16&255]]=*now;--now;}
case 2:{b[--cnt16[*now>>16&255]]=*now;--now;}
case 1:{b[--cnt16[*now>>16&255]]=*now;--now;}
}
tim=rep;
now=b+n-1;
while(tim--){
A[--cnt24[now[0]>>24]]=now[0];
A[--cnt24[now[-1]>>24]]=now[-1];
A[--cnt24[now[-2]>>24]]=now[-2];
A[--cnt24[now[-3]>>24]]=now[-3];
A[--cnt24[now[-4]>>24]]=now[-4];
A[--cnt24[now[-5]>>24]]=now[-5];
A[--cnt24[now[-6]>>24]]=now[-6];
A[--cnt24[now[-7]>>24]]=now[-7];now-=8;
}
switch(n&7){
case 7:{A[--cnt24[*now>>24]]=*now;--now;}
case 6:{A[--cnt24[*now>>24]]=*now;--now;}
case 5:{A[--cnt24[*now>>24]]=*now;--now;}
case 4:{A[--cnt24[*now>>24]]=*now;--now;}
case 3:{A[--cnt24[*now>>24]]=*now;--now;}
case 2:{A[--cnt24[*now>>24]]=*now;--now;}
case 1:{A[--cnt24[*now>>24]]=*now;--now;}
}
}
void sort(unsigned *a, int n) {
for(int i=0;i<n;i++)A[i]=a[i];
init_dAtA();
Sort();
for(int i=0;i<n;i++)a[i]=A[i];
}