#include <bits/stdc++.h>
#include "partition.h"
#include "grader.cpp"


using namespace std;

const int la = 1e7+2;
vector<int> solve(vector<int> a) {

    vector<int> b;
    vector<vector<int>> ch(la);
    for(int i = 0; i < a.size(); i ++ ) {
        ch[a[i]/100].push_back(i);
    }
    for(int i = 0; i < la; i ++ ) {
        if(ch[i].size() > 50000) {
            random_shuffle(ch[i].begin(), ch[i].end());
        }else {
            sort(ch[i].begin(), ch[i].end());
        }
        for(int &x : ch[i])b.push_back(x);
    }
    int n = a.size();
    vector<int> out;
    for(int r = 0 + (n%2==0); r < n; r += 2)
        out.push_back(b[r]);

    for(int r = n-2; r >= 0; r -= 2)
        out.push_back(b[r]);

    return out;
}
