#include "partition.h"
#include <algorithm>
#include <vector>
#include <utility>
#include <map>

using namespace std;

std::vector<int> solve(std::vector<int> A) {

    int N = (int)A.size();

    vector<pair<int,int>> V;
    

    map<int,vector<int>> cnt;

    for(int i=0;i<N;++i) {
        cnt[A[i]].push_back(i);
        //V.push_back({A[i],i});
    }

    //sort(V.begin(),V.end());

    int cur = 1;
    for(int i=0;i<=25;++i) {
        for(auto n:cnt[cur]) V.push_back({i,n});
        cur *= 2;
    }

    
    vector<int> B;
    vector<int> C;
    vector<int> rem;
    vector<int> res;

    for(int i=0;i<N;++i) {
        if (i != N-1 and V[i].first == V[i+1].first) {
            B.push_back(V[i].second);
            res.push_back(V[i+1].second);
            i++;
        }
        else rem.push_back(V[i].second);
    }

    int M = (int)rem.size();

    for(int i=0;i<M/2;++i) {
        B.push_back(rem[i]);
        res.push_back(rem[i+M/2]);

    }
    if (M % 2 == 1) res.push_back(rem[M-1]);
    

    
    for(int i=0;i<(int)B.size();++i) res.push_back(B[i]);


    return res;
}
