unsigned B[100000005];
unsigned s[255+1];
void radix_sort_(unsigned *A){ //a[i]>=0, -O2
const unsigned base = 255;
register int r = 100000000;
A-=1;
register 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=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=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=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=r;i>=1;--i)b[s[a[i]>>24&base]--]=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);
}