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

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

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

    int cnt;
    
    cnt = BUCKET;
    
    for (int i = 0; i < n; i++) {
        int bucket = a[i] % 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 (top[current]) {
            current = top[current];
            a[cnt] = current;
            cnt++;
        }
    }

    cnt = BUCKET;
    
    for (int i = 0; i < n; i++) {
        int bucket = a[i] / BUCKET % 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 (top[current]) {
            current = top[current];
            a[cnt] = current;
            cnt++;
        }
    }

    cnt = BUCKET;
    
    for (int i = 0; i < n; i++) {
        int bucket = a[i] / BUCKET / 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 (top[current]) {
            current = top[current];
            a[cnt] = current;
            cnt++;
        }
    }

    vector <int> ans;

    if (n % 2 == 0) {
        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;
}
