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

using namespace std;

using ll = long long;

#define ff  first
#define ss  second
#define pii pair<int, int>

#define sz(a)  (int)(a).size()
#define all(a) (a).begin(), (a).end()

vector<int> solve(vector<int> a) {
    int n = sz(a);
    ll S = accumulate(all(a), 0LL);
    
    pii p[n];
    for (int i = 0; i < n; i++) {
        p[i] = {a[i], i};
    }
    sort(p, p + n);

    vector<ll> sm(1 << n);
    int mn = INT_MAX, ansmk = -1;
    for (int mk = 1; mk < 1 << n; mk++) {
        int x = 31 - __builtin_clz(mk), cnt = __builtin_popcount(mk);
        assert(mk >> x & 1);
        sm[mk] = sm[mk ^ (1 << x)] + p[x].ff;

        if (sm[mk ^ (1 << x)] < S / 2.0 && !(sm[mk] < S / 2.0) && abs(n - 2 * cnt) < mn) {
            ansmk = mk;
            mn = abs(n - 2 * cnt);
        }
    }

    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (ansmk >> i & 1) ans.push_back(p[i].ss);
    }
    for (int i = 0; i < n; i++) {
        if (!(ansmk >> i & 1)) ans.push_back(p[i].ss);
    }

    // cout << "mn " << mn << ' ' << S << ' ' << ansmk << endl;
    ll SM = 0;
    int cnt = __builtin_popcount(ansmk);
    for (int i = 0; i < n; i++) {
        SM += a[ans[i]];

        if (i + 1 < cnt) assert(SM < S / 2.0);
        else assert(!(SM < S / 2.0));

        // cout << a[ans[i]] << ' ' << SM << endl;
    }

    return ans;
}