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