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

using namespace std;

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

//5 6 6 3 1 1 4 4 3
