#include "partition.h"
#include<bits/stdc++.h>
#define endl '\n'
#define out(x) #x<<" = "<<x<<" "
using namespace std;
unordered_map<int, int> mp;
const int MAX = 2 * 1e6 + 10;
int cnt[MAX], f[MAX], cnt2[MAX];
vector<int> solve(vector<int> A) {
    vector<int> ans, ans1, ans2;
    long long curr = 0, sum = 0, anss = 0;
    for(int i = 0; i < A.size(); i++){
        sum += A[i];
        if(mp[A[i]] == 0){
            mp[A[i]] = ++curr;
        }
        cnt[mp[A[i]]]++;
    }
    int m = 0, n = A.size(), br = 0;
    for(int i = 1; i <= curr; i++){
        if(m *  2 <= br){
            f[i]++;
            m ++;
        }
        m += cnt[i]/2;
        f[i] += cnt[i] / 2;
        br += cnt[i];
    }

    for(int i = 0; i < n; i++){
        if(cnt2[mp[A[i]]] < f[mp[A[i]]]){
            ans2.push_back(i);
            anss += A[i];
            cnt2[mp[A[i]]] ++;
        }else ans1.push_back(i);
    }

    if(2 * anss >= sum){
        //cout<<anss<<" "<<ans2
        ans = ans2;
    }else{
        ans = ans1;
        ans1 = ans2;
    }

    for(int i: ans1){
        ans.push_back(i);
    }

    for(int i = 0; i <= n; i++){
        cnt[i] = 0;
        cnt2[i] = 0;
        f[i] = 0;
        if(i < n) mp[A[i]] = 0;
    }
    return ans;
}
