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

vector<int> solve(vector<int> a) {
    unordered_map<int, int> Cnt;
    ll n = a.size();
    ll Sum = 0;
    for (auto& el : a) Sum += el;
    for (auto& el : a) Cnt[el]++;
    bool ok = true;
    for (auto& [el, cnt] : Cnt)
    {
        if (cnt % 2 != 0) ok = false;
    }
    if (ok)
    {
        vector<int> ans;
        unordered_map<int, 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++)
    {
        vector<pair<ll, ll>> values1, values2;
        for (ll i = n - 1; i >= 0; i--)
        {
            if ((mask & (1LL << i)))
            {
                values1.push_back({a[i], i});
            }
            else
            {
                values2.push_back({a[i], i});
            }
        }

        sort(values1.rbegin(), values1.rend());

        ll Ans = 0; bool fl = false;
        for (ll i = 0; i < values1.size(); i++)
        {
            Ans += values1[i].first;
            if (Ans * 2 >= Sum && i != values1.size() - 1) fl = true;
        }

        if (fl) continue;

        if (Ans * 2 >= Sum)
        {
            if (abs((ll)values1.size() - (ll)values2.size()) < BestAnsValue)
            {
                BestAnsValue = abs((ll)values1.size() - (ll)values2.size());
                ans.clear();
                for (ll i = 0; i < values1.size(); i++)
                {
                    ans.push_back(values1[i].second);
                }
                for (ll i = 0; i < values2.size(); i++)
                {
                    ans.push_back(values2[i].second);
                }
            }
        }
    }

    return ans;
}
