#include <bits/stdc++.h>
#define ss second
#define ff first
#define en end
#define be begin
#define ve vector
#define pb push_back
#define ppb pop_back
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
int v[2000000];
ve<int>st[100000];
ve<int>p;
void sortt(int n){
    ve<int>b;
    for (int i=0; i<n; i++){
        st[v[i]%100000].pb(i);
        b.pb(v[i]%100000);
    }
    ve<int>r;
    for (auto i:b){
        for (auto g:st[i])
            r.pb(g);
        st[i].clear();
    }
    b.clear();
    for (int i=0; i<n; i++){
        st[v[r[i]]/100000].pb(r[i]);
        b.pb(v[i]/100000);
    }
    for (auto i:b){
        for (auto g:st[i]){
            p.pb(g);
        }
        st[i].clear();
    }
}
ve<int> solve(ve<int>a){
    int  n=a.size();
    p.clear();
    long long sm=0;
    for (int  i=0; i<n; i++){
        v[i]=a[i];
    }
    sortt(n);
    ve<int>e;
    for (int i=0; i<n; i++){
        if (i%2==n%2) e.pb(i);
    }
    for (int i=0; i<n; i++){
        if (i%2!=n%2) e.pb(i);
    }
    return e;
}