#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();
    //cout<<q<<endl;
    if (a[0]==1 && a[n-1]==n && (n<3 || a[1]==2)){
        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;
    }
    ve<int>b;
    for (int i=0; i<=25; i++){
        b.pb(((1<<i))%1000);
    }
    int q=0;
    for (int i=0; i<n; i++){
        q=max(q,__builtin_popcount(a[i]));
    }
    if (q==1){
        for (int i=0; i<n; i++){
            st[a[i]%1000].pb(i);
        }
        ve<int>p;
        for (auto i:b){
            for (auto g:st[i]){
                p.pb(g);
            }
            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;

    }
    if (n<1000){
    pair<int ,int >v[n];
    ve<pair<int ,int >>c,d;
    long long  sm=0;
    for (int  i=0; i<n; i++){
        v[i]={a[i],i};
        sm+=a[i];
    }
    sm=(sm+1)/2;
    sort(v,v+n);
    for (int  i=0; i<n; i++){
        if (i%2==0) c.pb(v[i]);
        else d.pb(v[i]);
    }
    long long  q=0;
    for (int  i=0; i<c.size(); i++){
        q+=c[i].ff;
    }
    ve<int>e;
    if (q<=(sm)){
        for (auto g:d)
            e.pb(g.ss);
        for (auto g:c)
            e.pb(g.ss);

    }
    else {
        for (auto g:c)
            e.pb(g.ss);
        for (auto g:d)
            e.pb(g.ss);
    }
    return e;
    }
    int p[n];
    for (int i=0; i<n; i++){
        st[a[i]%100000].pb(i);
    }
    int r[n];
    int ri=0;
    int pi=0;
    for (int i=0; i<100000; i++){
        for (auto g:st[i])
            {
                r[ri]=g;
                ri++;
            }
        st[i].clear();
    }
    for (int i=0; i<n; i++){
        st[a[r[i]]/100000].pb(r[i]);
    }
    for (int i=0; i<=10000; i++){
        for (auto g:st[i]){
            {
                p[pi]=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;
}