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

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n = (int)A.size();
    long long sum[(1<<n)], mx[1<<n]; sum[0] = 0, mx[0] = -1;
    long long t = accumulate(A.begin(), A.end(), 0ll);
	//sort(b.begin(), b.end());
	int mn = n+1, pos = 0;
	for (int i = 1; i < (1<<n); ++i) {
		int x = 31-__builtin_clz(i);
		int pos = mx[(1<<x)^i];
		if (pos == -1 || A[pos] < A[x])mx[i] = x;
		else mx[i] = pos;
	}
    for (int i = 1; i < (1<<n); ++i) {
		long long last = A[mx[i]];
		sum[i] = sum[(1<<mx[i])^i]+last;
		//if (i == 16)cout << b[4].first << endl;
		if (2ll*sum[i] >= t && 2ll*(sum[i]-last) < t && abs(n-2*__builtin_popcount(i)) < mn) {
			mn = abs(n-2*__builtin_popcount(i));
			pos = i;
		}
	}
	//cout << mn << " " << pos << endl;
	vector<int> c;
	for (int i = 0; i < n; ++i)
		if ((1<<i)&pos && i != mx[pos])c.push_back(i);
	if (mx[pos] != -1)c.push_back(mx[pos]);
	for (int i = 0; i < n; ++i)
		if (!((1<<i)&pos))c.push_back(i);
	return c;
}

//5 6 6 3 1 1 4 4 3
