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

std::vector<int> solve(std::vector<int> A){
    map<int64_t,int64_t> mp, cnt, mt;
    int64_t n = A.size();
    int64_t cur = 0;
    vector<int> a = A;
    for(auto &i : A) cnt[i]++;
    set<int64_t> st;
    for(int64_t i = 0; i < n; i++){
        if(cnt[A[i]] > 1){
            a[i] = (cnt[a[i]] & 1 ? cur : -1);
            cnt[A[i]]--;
            if(a[i] != -1) cur++;
        } else{
            //cerr << a[i] << endl;
            st.insert(A[i]);
            a[i] = -2;
        }
    }
    auto A1 = A;
    A.clear();
    for(auto &i : st) A.push_back(i);
    map<int,int> mk;
    int mx = *st.rbegin();
    mk[*st.begin()] = -1;
    st.erase(st.begin());
    if(st.size() == 1){
        mk[*st.begin()] = cur;
        cur++;
    } else{
        int p = st.size()/2;
        while(p--){
            mk[*st.begin()] = cur;
            cur++;
            st.erase(st.begin());
        }
        for(auto &i : st) mk[i] = -1;
        mk[mx] = cur;
        cur++;
    }
    for(int i = 0; i < a.size(); i++){
        if(a[i] == -2){
            a[i] = mk[A1[i]];
        }
        if(a[i] == -1){
            a[i] = cur;
            cur++;
        }
    }
    return a;
}