#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<int> solve(vector<int> a) {
    vector<int> Cnt(3e7+1);
    ll n = a.size();
    ll Sum = 0;
    for (auto& el : a) Sum += el;
    for (auto& el : a) Cnt[el]++;
    bool ok = true;
    for (ll i = 0; i < 1e7+1; i++)
    {
        if (Cnt[i] % 2 != 0) ok = false;
    }
    if (ok)
    {
        vector<int> ans;
        vector<int> Cnt2 = Cnt;
        unordered_set<int> st;
        for (ll i = 0; i < n; i++)
        {
            if (Cnt2[a[i]] > Cnt[a[i]] / 2) { ans.push_back(i); Cnt2[a[i]]--; st.insert(i);}
        }
        for (ll i = 0; i < n; i++)
        {
            if (st.find(i) == st.end()) { ans.push_back(i);}
        }
        return ans;
    }

    ll BestAnsValue = n+1; vector<int> ans;
    for (ll mask = 0; mask < (1LL << (n)); mask++)
    {
        ll cnt = 0, Ans = 0;
        for (ll i = n - 1; i >= 0; i--)
        {
            if ((mask & (1LL << i)))
            {
                cnt++;
                Ans += a[i];
            }
        }
        //cout << abs(cnt - (n - cnt)) << ' ' << cnt << ' ' << Ans << endl;
        if (Ans * 2 >= Sum)
        {
            if (abs(cnt - (n - cnt)) < BestAnsValue)
            {
                BestAnsValue = abs(cnt - (n - cnt));
                ans.clear();
                for (ll i = n - 1; i >= 0; i--)
                {
                    if ((mask & (1LL << i)) != 0)
                    {
                        ans.push_back(i);
                    }
                }
                for (ll i = n - 1; i >= 0; i--)
                {
                    if ((mask & (1LL << i)) == 0)
                    {
                        ans.push_back(i);
                    }
                }
            }
        }
    }

    return ans;
}
