#include "partition.h"
#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){
            cnt[A[i]]--;
            a[i] = (cnt[a[i]] & 1 ? cur : -1);
            if(a[i] != -1) cur++;
            A[i] = -1;
        } else{
            //cerr << a[i] << endl;
            st.insert(a[i]);
            a[i] = -2;
        }
    }
    int64_t subsm = 0, sum = 0;
    for(auto &i : st) sum += i;
    set<int64_t> 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 << " " << cur << endl;
        cur++;
        pos--; 
    }
    set<int64_t> stt;
    for(auto &i : st){
        if(stm.find(i) == stm.end()){
            stt.insert(i);
            //cerr << i << endl;
        }
    }
    int64_t cnt1 = st.size()-stt.size(), cnt2 = 0;
    for(auto &i : stt){
        if(cnt2 >= cnt1){
            mt[i] = cur;
            cnt1++;
            cur++;
        } else{
            mt[i] = -1;
            cnt2++;
        }
        //cerr << i << " " << a[i] << endl; 
    }
    for(int64_t i = 0; i < n; i++){
        if(a[i] == -2){
            a[i] = mt[A[i]];
        }
    }
    for(int64_t i = 0; i < n; i++){
        if(a[i] == -1){
            a[i] = cur;
            cur++;
        }
    }
    //for(auto &i : a) cout << i << " ";
    return a;
}