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

#define int long long

std::vector<int32_t> solve(std::vector<int32_t> a) {
    int n = a.size(), total = accumulate(a.begin(), a.end(), 0ll);
    int ub = (total + 1) / 2;
    vector<int32_t> ans;
    int best = n + 1;
    for (int mask = 0; mask < 1 << n; mask++) {
        vector<int> v;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask >> i & 1) {
                v.push_back(i);
                sum += a[i];
            }
        }
        if (sum < ub) {
            continue;
        }
        sort(v.begin(), v.end(), [&](int i, int j) {
            return a[i] < a[j];
        });
        sum = 0;
        int cnt = 0;
        for (int i : v) {
            sum += a[i];
            cnt++;
            if (sum >= ub) {
                break;
            }
        }
        if (abs(cnt - (n - cnt)) < best) {
            ans.clear();
            for (int i : v) {
                ans.push_back(i);
            }
            for (int i = 0; i < n; i++) {
                if (!(mask >> i & 1)) {
                    ans.push_back(i);
                }
            }
            best = abs(cnt - (n - cnt));
        }
    }
    return ans;
}