!Kirk-patrick sort (works only for int32 why??)

#ifdef ONPC
    # define _GLIBCXX_DEBUG
    #define deb(a) cerr << "========" << #a << " = " << a << endl;
#else
    #define deb(a)
#endif
#define sz(a) (int)(a).size()


#include <bits/stdc++.h>

using namespace std;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(time(0));

typedef long long ll;

template<typename T>
vector<T> count_sort(vector<T> &x)
{
    int pos = max_element(x.begin(), x.end()) - x.begin();
    T mx = x[pos];
    vector<int> cnt(mx + 1, 0);
    for (T it : x)
        cnt[it]++;
    vector<T> ans;
    for (int i = 0; i <= mx; i++)
        for (int j = 0; j < cnt[i]; j++)
            ans.push_back(i);
    return ans;
}

template<typename T>
vector<T> my_sort(int k, vector<T> &x)
{
    T one = 1;
    int n = sz(x);
    if (n <= 1)
        return x;
    if (k <= 1 || n >= (one << (1 << k)))
        return count_sort(x);
    vector<T> a(n), b(n), as, result;
    unordered_map<T, vector<T> > q;
    for (int i = 0; i < n; i++)
    {
        b[i] = (x[i] & ((one << (one << (k - 1))) - 1));
        a[i] = (x[i] >> (one << (k - 1)));
        q[a[i]].push_back(b[i]);
    }
    for (auto &p : q)
        as.push_back(p.first);
    as = my_sort(k - 1, as);
    for (T val : as)
    {
        vector<T> &bs = q[val];
        int i = max_element(bs.begin(), bs.end()) - bs.begin();
        T mx = bs[i];
        swap(bs[i], bs.back());
        bs.pop_back();
        bs = my_sort(k - 1, bs);
        bs.push_back(mx);
        for (T j : bs)
            result.push_back((val << (one << (k - 1))) | j);
    }
    return result;
}

int gen()
{
    return abs((int)rnd());
}

const ll INF = 1e9 + 7;

int solve()
{
    int n;
    if (!(cin >> n))
        return 1;
   /* while (true)
    {
        n = gen() % 100 + 1;*/
        vector<ll> v(n);
        for (ll &i : v)
            cin >> i, i += INF;
        vector<ll> u = my_sort(5, v);
        //sort(v.begin(), v.end());
        /*if (v != u)
        {
            cout << "mem\n";
            return 1;
        }*/
        for (ll i : u)
            cout << i - INF << ' ';
        cout << '\n';
    //}
    return 1;
}
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int TET = 1e9;
    //cin >> TET;
    while (TET--)
    {
        if (solve())
            break;
        #ifdef ONPC
            cout << "\n__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
    return 0;
}