#include<bits/stdc++.h>
#include "partition.h"

using ll = long long;

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    ll S = std::accumulate(a.begin(), a.end(), 0ll);
    int mx = std::max_element(a.begin(), a.end()) - a.begin();
    std::vector<int> perm(n);
    std::iota(perm.begin(), perm.end(), 0);
    std::sort(perm.begin(), perm.end(), [&](int x, int y) {
        return a[x] > a[y];
    });
    int msk = -1, opt = n + 1;
    auto chk = [&](auto chk, int i, int mask, ll s) -> void {
        if (s > (S - 1) / 2) return;
        if (i == n) {
            int cnt = __builtin_popcount(mask);
            int diff = std::abs(cnt + 1 - (n - cnt - 1));
            if (diff < opt) {
                msk = mask;
                opt = diff;
            }
            return;
        }
        int j = perm[i];
        if (j != mx) {
            chk(chk, i + 1, mask | (1 << j), s + a[j]);
        }
        chk(chk, i + 1, mask, s);
    };
    chk(chk, 0, 0, 0);
    std::vector<int> ret;
    for (int i = 0; i < n; ++i) {
        if (msk >> i & 1) ret.push_back(i);
    }
    ret.push_back(mx);
    for (int i = 0; i < n; ++i) {
        if (i == mx) continue;
        if (~msk >> i & 1) ret.push_back(i);
    }
    return ret;
}