#include <algorithm>
#pragma GCC optimize("3,inline,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const int ful = (1 << 16) - 1;
int tt[ful + 1];
unsigned *tmp = new unsigned[100000000];
void sort(unsigned *a, int n) {
for (register int i = 0; i < n; ++i) ++tt[a[i] & ful];
for (register int i = 1; i <= ful; ++i) tt[i] += tt[i - 1];
for (register int i = n - 1; ~i; --i) tmp[--tt[a[i] & ful]] = a[i];
std::swap(a, tmp);
for (register int i = 0; i <= ful; ++i) tt[i] = 0;
for (register int i = 0; i < n; ++i) ++tt[(a[i] >> 16) & ful];
for (register int i = 1; i <= ful; ++i) tt[i] += tt[i - 1];
for (register int i = n - 1; ~i; --i) tmp[--tt[(a[i] >> 16) & ful]] = a[i];
std::swap(a, tmp);
}