#include "partition.h"
#include "bits/stdc++.h"

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    unordered_map<int,int>cnt;
    for(int i=0;i<n;i++)
        cnt[A[i]]++;
    unordered_map<int,int>loc;
    vector<int>ans,bck;
    vector<int>d;
    for(int i=0;i<n;i++){
        loc[A[i]]++;
        if(loc[A[i]]<=cnt[A[i]]/2){
            ans.push_back(i);
        } else {
            if (cnt[A[i]] % 2 == 1 and loc[A[i]] == cnt[A[i]])
                d.push_back(i);
            else
                bck.push_back(i);
        }
    }
    if(not d.empty()){
        sort(begin(d),end(d),[&](int i, int j){return A[i]<A[j];});

        for (int i = 0; i < (int)d.size() / 2 - 1; i ++){
            ans.push_back(d[i]);
        }
        ans.push_back(d.back());
    }
    for(int i : bck)ans.push_back(i);
    if(not d.empty()){

        for(int i = max(0,(int)d.size()/2-1);i<(int)d.size()-1;i++){
            ans.push_back(d[i]);
        }
    }
    return ans;
}