#include <bits/stdc++.h>
using namespace std;
int ans = 0;
int k1 = 0;
void rec(int pos, int k, vector<int> &a, int sum, int sm){
    if(sum >= sm/2){
        int ns = 0;
        while(k > 0){
            ns += k % 2;
            k /= 2;
        }
        int p = llabs(a.size()-ns);
        if(p < ans){
            k1 = k;
        }
        ans = min(ans, p);
        return;
    }
    if(pos != a.size()){
        for(int i = 0; i < a.size(); i++){
            if(k & (1<<i) != 0) continue;
            rec(pos+1,k&(1<<i),a,sum+a[i],sm);
        }
    }
}

std::vector<int> solve(std::vector<int> A){
    using ll = long long;
    ll n = A.size();
    if(n <= 7){
        int sum = accumulate(A.begin(),A.end(),0);
        rec(0,0,A,sum,0);
        int cur = 0;
        vector<int> a(n, -1);
        for(int i = 0; i < n; i++){
            if((1<<i) & k1 != 0){
                a[i] = cur;
                cur++;
            }
        }
        for(int i = 0; i < n; i++){
            if(a[i] == -1){
                a[i] = cur;
                cur++;
            }
        }
        return a;
    }
    vector<ll> a(n, -1);
    map<ll,ll> mp, m1, m2, ms; 
    for(auto &i : A) mp[i]++;
    ll cur = 0;
    for(ll i= 0 ; i < n; i++){
        if(m1[A[i]] < (mp[A[i]]/2)){
            a[i] = cur;
            cur++;
            m1[A[i]]++;
        }
    }
    for(auto &i : a){
        if(i == -1){
            i = cur;
            cur++;
        }
    }
    vector<int> ans;
    for(auto &i : a) ans.push_back(i);
    return ans;
}
