#include <iostream>
#include <cstdio>
#define MAX 1000000005
using namespace std;
const int INF = 0xffff + 1;
int aa[MAX], bb[MAX], cc[MAX];
int x[MAX], y[MAX], t[INF];
void sort(unsigned *a, int n) {
int i;
for (i = 1; i <= n; ++i)
{
cc[i] = a[i];
bb[i] = cc[i] / INF;
aa[i] = cc[i] % INF;
}
for (i = 0; i < INF; ++i)
t[i] = 0;
for (i = 1; i <= n; ++i)
++t[aa[i]];
for (i = 1; i < INF; ++i)
t[i] += t[i - 1];
for (i = n; i >= 1; --i)
x[t[aa[i]]--] = i;
for (i = 0; i < INF; ++i)
t[i] = 0;
for (i = 1; i <= n; ++i)
++t[bb[x[i]]];
for (i = 1; i < INF; ++i)
t[i] += t[i - 1];
for (i = n; i >= 1; --i)
y[t[bb[x[i]]]--] = x[i];
for (i = 1; i <= n; ++i)
a[i] = cc[y[i]];
}