#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){
            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;
        }
    }
    int64_t subsm = 0, sum = 0;
    for(auto &i : st) sum += i;
    set<int64_t> stm;
    map<int,int> used;
    int sz = 0;
    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;
        used[*pos] = 1;
        st.erase(*pos);
        sz++;
        //cerr << *pos << " " << cur << endl;
        cur++;
        pos--; 
    }
    //cerr << "DBG\n";
    int64_t cnt1 = sz, cnt2 = 0;
    while(cnt1 > 0){
        auto pos = st.end();
        pos--;
        mt[*pos] = -1;
        cnt1--;
        st.erase(*pos);
    }
    //cerr << "DBG\n";
    for(auto &i : st){
        if(cnt1 & 1){
            mt[i] = cur;
            cur++;
        } else{
            mt[i] = -1;
        }
        cnt1++;
        //cerr << i << " " << a[i] << endl; 
    }
    //cerr << "DBG\n";
    for(int64_t i = 0; i < n; i++){
        if(a[i] == -2){
            a[i] = mt[A[i]];
        }
    }
    map<int,int> mk;
    set<int> mn;
    for(int64_t i = 0; i < n; i++){
        if(a[i] != -1 and a[i] != -2){
            mn.insert(A[i]);
            //cerr << a[i] << endl;
        }
    }
    cur = 0;
    for(auto &i : mn){
        mk[i] = cur;
        cur++;
    }
    for(int64_t i = 0; i < n; i++){
        if(a[i] != -1 and a[i] != -2){
            a[i] = mk[A[i]];
            //cerr << a[i] << endl;
        }
    }
    for(int64_t i = 0; i < n; i++){
        if(a[i] == -1){
            a[i] = cur;
            cur++;
            //cerr << a[i] << endl;
        }
    }
    //cerr << "DBG\n";
    vector<vector<int>> v(n);
    for(int i = 0; i < n; i++){
        v[a[i]].push_back(A[i]);
    }
    int sum1 = 0;
    int cnt3 = 0;
    for(int i = 0; i < n; i++){
        sum1 += v[i][0];
        cnt3++;
        if(sum1 >= (sum+sum%2)/2) break;
    }
    //cerr << abs(2*cnt3-n) << endl << cnt3 << endl;
    //for(auto &i : a) cout << i << " ";
    return a;
}