#include <iostream>
#include "partition.h"
using namespace std;

const int MAXN = 3e6 + 10, BUCKET = 1e3;
int top[MAXN], to[MAXN], a[MAXN];

inline void radix(int n, int d) {
    int cnt = BUCKET;

    for (int i = 0; i < BUCKET; i++) {
        top[i] = i;
        to[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int bucket = (a[i] / d) % BUCKET;
        to[top[bucket]] = cnt;
        top[bucket] = cnt;
        top[cnt] = 0;
        cnt++;
    }

    cnt = 0;

    for (int i = 0; i < BUCKET; i++) {
        int current = i;

        while (to[current]) {
            current = to[current];
            a[cnt++] = current;
        }
    }
}

vector <int> solve(vector <int> v) {
    int n = v.size();
    
    for (int i = 0; i < n; i++) {
        a[i] = i;
    }

    radix(n, 1);
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';
    radix(n, BUCKET);
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';
    radix(n, BUCKET * BUCKET);
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    cout << '\n';

    vector <int> ans;
    ans.reserve(n);

    if (n % 2) {
        for (int i = 0; i < n; i += 2) {
            ans.push_back(a[i]);
        }
    
        for (int i = 1; i < n; i += 2) {
            ans.push_back(a[i]);
        }

        return ans;
    }
    
    for (int i = 1; i < n; i += 2) {
        ans.push_back(a[i]);
    }

    for (int i = 0; i < n; i += 2) {
        ans.push_back(a[i]);
    }

    return ans;
}
