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

using namespace std;

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

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

    vector<pair<int,int>> V;
    

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

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

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

    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);
            C.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]);
        C.push_back(rem[i+M/2]);

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

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

    return res;
}
