#include "bits/stdc++.h"
#include "partition.h"
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mod 1000000007
#define N 24
#define maxn 200005

ll sm=0,answer=1e9;
vector<int> v,ans,cur;

void f(int id){
	if(id==v.size()){
		ll s=0,cnt=0;
		for(int i=0; i<cur.size(); i++){
			s+=v[cur[i]];
			cnt++;
			if(s>=sm)break;
		}
		if(s>=sm and answer>abs((int)v.size()-cnt*2)){
			answer=abs((int)v.size()-cnt*2);
			ans.clear();
			for(int i=0; i<cnt; i++)ans.pb(cur[i]);
		}
		return;
	}
	f(id+1);
	cur.pb(id);
	f(id+1);
	cur.pop_back();
}

std::vector<int> solve(std::vector<int> A) {
	answer=1e9;
	v.clear();
	sm=0;
	for(int i=0; i<A.size(); i++)v.pb(A[i]),sm+=A[i];
	sm=sm/2+sm%2;
	f(0);
	map<int,bool> m;
	vector<int> aa;
	for(int i=0; i<ans.size(); i++)m[ans[i]]=true,aa.pb(ans[i]);
	for(int i=0; i<A.size(); i++)if(!m[i])aa.pb(i);
	ans.clear();
	return aa;
}