#include <iostream>
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include "partition.h"
using namespace std;

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

inline void radix(int n, int d, const vector <int>& v) {
    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 = (v[a[i]] / d) % BUCKET;
        to[top[bucket]] = cnt;
        top[bucket] = cnt;
        value[cnt] = a[i];
        to[cnt++] = 0;
    }

    cnt = 0;

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

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

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

    radix(n, 1, v);
    radix(n, BUCKET, v);
    radix(n, BUCKET * BUCKET, v);

    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;
}
/**
1
9
5 6 6 3 1 1 4 4 3
 */