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

#define speedup cin.tie(0) -> sync_with_stdio(0)
#define all(x) begin(x), end(x)
#define pb push_back
#define vc vector

using ll = long long;
template<class T> bool chmin(T &a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> bool chmax(T &a, T b) {if (a < b) {a = b; return 1;} return 0;}
vc<int> solve(vc<int> a) {
    ll s = accumulate(all(a), 0ll), t = (s + 1) / 2;
	int n = a.size(), ans = n + 1;
	
	ll ms = -1, msi = -1;
	for (int mask = 1; mask < (1 << n); mask++) {
		int sum = 0, mx = -1, id = -1;
		for (int i = 0; i < n; i++) if (mask >> i & 1) {
			sum += a[i];
			if (chmax(mx, a[i])) id = i;
		}
		
		if (sum >= t && sum - mx < t) {
			int res = __builtin_popcount(mask);
			res = abs(res + res - n);
			if (chmin(ans, res)) {
				ms = mask;
				msi = id;
			}
		}
	}
	
	vc<int> v; ms -= (1 << msi);
	for (int i = 0; i < n; i++) if (ms >> i & 1) v.pb(i);
	
	v.pb(msi);
	ms += (1 << msi);
	for (int i = 0; i < n; i++) if (!(ms >> i & 1)) v.pb(i);
	
	return v;
}
