#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;
ve<int>st[100000];
ve<int> solve(ve<int>a){
    int  n=a.size();
    int p[n];
    ve<int>b;
    for (int i=0; i<n; i++){
        st[a[i]%100000].pb(i);
        b.pb(a[i]%100000);
    }
    int r[n];
    int ri=0;
    int pi=0;
    for (auto i:b){
        for (auto g:st[i])
            {
                r[ri]=g;
                ri++;
            }
        st[i].clear();
    }
    b.clear();
    for (int i=0; i<n; i++){
        st[a[r[i]]/100000].pb(r[i]);
        b.pb(a[i]/100000);
    }
    for (auto i:b){
        for (auto g:st[i]){
            {
                p[ri]=g;
                pi++;
            }
        }
        st[i].clear();
    }
    ve<int>e;
    for (int i=0; i<n; i++){
        if (i%2!=n%2) e.pb(p[i]);
    }
    for (int i=0; i<n; i++){
        if (i%2==n%2) e.pb(p[i]);
    }
    return e;
}