
#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
const int LG = 21;
using ll = long long;
vector<int> solve(vector<int> a) {
    int n = a.size();
    ll full = 0;
    for (int i = 0; i < n; i++) {
        full += a[i];
    }
    vector<int> ans(n);
    int best = INT_MAX;
    int endMask = 1 << n;
    for (int mask = 0; mask < endMask; mask++) {
        ll s = 0;
        int cnt = 0;
        int mx = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                s += a[i];
                mx = max(a[i], mx);
                cnt++;
            }
        }
        if (s * 2 >= full  && 2 * (s - mx) < full) {
            if (abs(cnt - (n - cnt)) < best) {
                best = abs(cnt - (n - cnt));
                ans.resize(0);
                vector<int> mxIdx;
                for (int i = 0; i < n; i++) {
                    if (mask & (1 << i)) {
                        if (a[i] != mx) {
                            ans.push_back(i);
                        } else {
                            mxIdx.push_back(i);
                        }
                    }
                }
                for (int i = 0; i < mxIdx.size(); i++) {
                    ans.push_back(mxIdx[i]);
                }

                for (int i = 0; i < n; i++) {
                    if (!(mask & (1 << i))) {
                        ans.push_back(i);
                    }
                }
            }
        }
    }
    return ans;
}
