#define base 255
unsigned B[100000005];
unsigned s[base+1];
void radix_sort_(unsigned *A,int l,int r){ //a[i]>=0, -O2
A+=l-1;r-=l-1;l=1;
unsigned *a=A,*b=B;
{
for (int i=0;i<=base;++i)s[i]=0;
for (int i=1;i<=r;++i)++s[a[i]&base];
for (int i=1;i<=base;++i)s[i]+=s[i-1];
for (int i=0;i<=base;++i)++s[i];
for (int i=r;i>=1;--i)b[--s[a[i]&base]]=a[i];
unsigned *tmp=a;a=b;b=tmp;
}
{
for (int i=0;i<=base;++i)s[i]=0;
for (int i=1;i<=r;++i)++s[a[i]>>8&base];
for (int i=1;i<=base;++i)s[i]+=s[i-1];
for (int i=0;i<=base;++i)++s[i];
for (int i=r;i>=1;--i)b[--s[a[i]>>8&base]]=a[i];
unsigned *tmp=a;a=b;b=tmp;
}
{
for (int i=0;i<=base;++i)s[i]=0;
for (int i=1;i<=r;++i)++s[a[i]>>16&base];
for (int i=1;i<=base;++i)s[i]+=s[i-1];
for (int i=0;i<=base;++i)++s[i];
for (int i=r;i>=1;--i)b[--s[a[i]>>16&base]]=a[i];
unsigned *tmp=a;a=b;b=tmp;
}
{
for (int i=0;i<=base;++i)s[i]=0;
for (int i=1;i<=r;++i)++s[a[i]>>24&base];
for (int i=1;i<=base;++i)s[i]+=s[i-1];
for (int i=0;i<=base;++i)++s[i];
for (int i=r;i>=1;--i)b[--s[a[i]>>24]]=a[i];
unsigned *tmp=a;a=b;b=tmp;
}
if (a!=A)for (int i=1;i<=r;++i)A[i]=a[i];
}
void sort(unsigned *a, int n){
radix_sort_(a, 0, n-1);
}