#include<vector>
#include<iostream>
#include<algorithm>
#include"partition.h"
using namespace std;
using ll = long long;
std::vector<int> solve(std::vector<int> A) {
	ll n = A.size();
	ll mn = 1e9, s = 0, tiv = -1;
	for (ll i = 0; i < n; i++)s += A[i];
	for (ll i = 0; i < (1 << n);i++) {
		ll sum = 0,  cnt = 0;
		int mx = 0;
		for (ll j = 0; j < n; j++) {
			if (i & (1 << j)) {
				sum += A[j];
				cnt++;
				mx = max(mx, A[j]);
			}
		}
		if (sum >= (s + 1) / 2 && sum - mx < (s + 1) / 2) {
			if (abs(cnt - (n - cnt)) < mn) {
				mn = abs(cnt - (n - cnt));
				tiv = i;
			}
		}
	}
	vector<int>ans;
		vector<pair<ll, ll>>v;
		for (ll j = 0; j < n; j++) {
			if (tiv & (1 << j)) {

				v.push_back({ A[j],j });
			}
		}
		sort(v.begin(), v.end());
		for (auto x : v) {
			ans.push_back(x.second);
		}
		for (ll j = 0; j < n; j++) {
			if ((tiv & (1 << j))==0) {
				ans.push_back(j);
			}
		}
		

	
	return ans;
	
}
