#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<int> a=A;
    vector<int> ans(n);
    map<int,int> mp;
    int j=0;
    int o=n-1;
    for(int i=0;i<n;i++){
        mp[a[i]]++;
    }
    map<int,int> m2;
    vector<pair<int,int>> v;
    for(int i=0;i<n;i++){
        if(mp[a[i]]>=2){
            m2[a[i]]++;
            if(m2[a[i]]%2==1 and m2[a[i]]!=mp[a[i]]){
                ans[j]=i;
                j++;
            }
            else if(m2[a[i]]%2==0){
                ans[o]=i;
                o--;
            }
            else v.push_back({a[i],i});
        }
        else v.push_back({a[i],i});
    }
    sort(v.begin(),v.end());
    for(int i=j;i<=o;i++){
        if(i+1==(n+1)/2){
            ans[i]=v[v.size()-1].second;
        }
        else if(i+1<(n+1)/2){
            ans[i]=v[i-j].second;
        }
        else{
            ans[i]=v[i-j-1].second;
        }
    }
    if(n==1)ans[0]=0;
    return ans;
}