#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();
    int msk = -1, opt = n + 1;
    for (int mask = 0; mask < 1 << n; ++mask) {
        if (mask >> mx & 1) continue;
        ll sum = 0;
        for (int i = 0; i < n; ++i) {
            if (mask >> i & 1) sum += a[i];
        }
        if ((S + 1) / 2 - a[mx] <= sum && sum <= (S - 1) / 2) {
            int cnt = __builtin_popcount(msk);
            int diff = std::abs(cnt + 1 - (n - cnt - 1));
            if (diff < opt) {
                msk = mask;
                opt = diff;
            }
        }
    }
    std::vector<int> perm;
    for (int i = 0; i < n; ++i) {
        if (msk >> i & 1) perm.push_back(i);
    }
    perm.push_back(mx);
    for (int i = 0; i < n; ++i) {
        if (~msk >> i & 1) perm.push_back(i);
    }
    return perm;
}