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

std::vector<int> solve(std::vector<int> A){
    map<int,int> mp, cnt, mt;
    int n = A.size();
    int cur = 0;
    vector<int> a = A;
    for(auto &i : A) cnt[i]++;
    set<int> st;
    for(int i = 0; i < n; i++){
        if(mp[A[i]] < cnt[A[i]]-1){
            mp[A[i]]++;
            a[i] = (mp[a[i]] & 1 ? cur : -1);
            A[i] = -1;
            cur++;
        } else{
            st.insert(a[i]);
            a[i] = -2;
        }
    }
    int subsm = 0, sum = 0;
    for(auto &i : st) sum += i;
    set<int> stm;
    while(subsm < (sum+sum%2)/2){
        auto pos = st.lower_bound((sum+sum%2)/2-subsm);
        if(pos == st.end()) pos--;
        subsm += *pos;
        mt[*pos] = cur;
        stm.insert(*pos);
        //cerr << *pos << endl;
        cur++;
        pos--; 
    }
    set<int> stt;
    for(auto &i : st){
        if(stm.find(i) == stm.end()){
            stt.insert(i);
        }
    }
    int cnt1 = st.size()-stt.size(), cnt2 = 0;
    for(auto &i : stt){
        if(cnt2 >= cnt1){
            a[i] = cur;
            cnt1++;
        } else{
            a[i] = -1;
            cnt2++;
        }
    }
    for(int i = 0; i < n; i++){
        if(a[i] == -2){
            a[i] = mt[A[i]];
        }
    }
    for(int i = 0; i < n; i++){
        if(a[i] == -1){
            a[i] = cur;
            cur++;
        }
    }
    //for(auto &i : a) cout << i << " ";
    return a;
}

// signed main(){
//     cin.tie(0)->sync_with_stdio(0);
//     int _; cin >> _;
//     while(_--){
//         int n; cin >> n;
//         vector<int> a(n);
//         for(auto &i : a) cin >> i;
//         auto p = solve(a);
//     }
// }