#include <bits/stdc++.h>
#define INF 1000000000
#define fi first
#define se second
#include "partition.h"
using namespace std;

vector<int> solve(vector<int> a) {
    int tot=0, n=a.size(), minim=INF, i;
    vector<int>ans;
    map<int, int> h, nr;
    h.clear();
    nr.clear();
    vector<int>v, t;
    for (auto x:a) tot+=x;
    if (n<=7) {
        for (i=0; i<n; i++) v.push_back(i);
        do {
            int sum=0, nrpack=0;
            for (auto x:v) {
                sum+=a[x];
                nrpack++;
                if (sum*2>=tot) break;
            }
            if (abs(nrpack*2-n)<minim) {
                minim=nrpack*2-n;
                ans=v;
            }
        } while (next_permutation(v.begin(), v.end()));
        return ans;
    }
    for (auto x:a) {
        h[x]++;
    }
    t.resize(n);
    for (i=0; i<n; i++) t[i]=0;
    for (i=0; i<n; i++) {
        nr[a[i]]++;
        if (nr[a[i]]*2>h[a[i]]) continue;
        ans.push_back(i);
        t[i]=1;
    }
    for (i=0; i<n; i++) {
        if (t[i]==0) ans.push_back(i);
    }
    return ans;
}

