#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
vector <int> ctz((1<<25)+1);
std::vector<int> solve(std::vector<int> A){
    int n=A.size();
    vector <pair <int,int> > a(n+5);
    vector <bool> vis(n+5,0);
    vector <int> mp(200,0);
    for(int i=1;i<=n;i++){
        a[i]=make_pair(A[i-1],i);
    }
    vector <int> vec,vec1;
    vector <pair <int,int> > b,c,vect[26];
    for(int i=1;i<=n;i++){
        int x=ctz[a[i].ff];
        if(mp[x]>0){
            vis[mp[x]]=1;
            vis[i]=1;
            vec.pb(a[mp[x]].ss);
            vec1.pb(a[x].ss);
            mp[x]=0;
        }else{
            mp[x]=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            c.pb(a[i]);
        }
    }
    if(c.size()>26){
        assert(0);
    }
    for(auto u:c){

        int x=ctz[u.ff];
        vect[x].pb(u);
    }
    for(int i=0;i<=25;i++){
        for(auto u:vect[i]){
            b.pb(u);
        }
    }

    // for(auto u:b){
    //     // cout<<u.ff<<" "<<u.ss<<endl;
    // }
    for(int i=0;i<int(b.size())/2 -1;i++){
        // cout<<"HERE"<<endl;
        vec.pb(b[i].ss);
    }
    vec.pb(b.back().ss);
        // cout<<"HERE1"<<endl;
    for(int i=max(0,int(b.size())/2-1);i<int(b.size())-1;i++){
        // cout<<"HERE2"<<endl;
        vec1.pb(b[i].ss);
    }
    for(auto u:vec1){
        vec.pb(u);
    }
    for(auto &u:vec){
        u--;
    }
    return vec;
}
// int main () {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     int t;
//     cin >> t ;
//     for (int test=1; test<=t; test++) {
//         int n;
//         cin >> n ;
//         vector <int> a(n);
//         for (int i=0; i<n; i++) {
//             cin >> a[i] ;
//         }

//         for (auto ind : solve(a)) {
//             cout << ind << " ";
//         }
//         cout << endl ;
//     }
//     cout << endl ;
//     return 0;
// }
