#include "partition.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;
const ll N=2e6;
vector <int> ans,nw,nww;
int pw[20],indd;
std::vector<int> solve(std::vector<int> a) {
    
    ll n=a.size();
    ans.clear();
	int sum=0;
	
    for (int i=0; i<n; i++){
    sum+=a[i]; 
    	
	}
	pw[0]=1;
	for (int i=1; i<=n; i++) pw[i]=pw[i-1]*2;
	
	int mxx,z,s,dif,mx=n+1,answ=0;
	for (z=0; z<=pw[n]; z++){
		
		nw.clear(); nww.clear();
		mxx=0; s=0;
		indd=-1;
		for (int i=0; i<a.size(); i++){
			if ((pw[i]&z)==0){
				nww.pb(i); continue; }
			nw.pb(i); 
			mxx=max(mxx,a[i]); if (mxx==a[i]) indd=i; s+=a[i];
		}
		if (s<(sum+1)/2) continue;
		if ((s-mxx)>=(sum+1)/2) continue;
		dif=nw.size()-nww.size();
		if (dif<0) dif*=(-1);
	//	cout<<dif<<endl;
		if (dif>=mx) continue; mx=dif; answ=z;
		
		
	}
	z=answ;
	nw.clear(); nww.clear();
	for (int i=0; i<a.size(); i++){
			if ((pw[i]&z)==0){
				nww.pb(i); continue; }
			nw.pb(i); 
			mxx=max(mxx,a[i]); if (mxx==a[i]) indd=i; 
		}
		int k=-1;
		for (int i=0; i<nw.size(); i++){
			if (indd==nw[i]) continue;
			ans.pb(nw[i]);
		}
		ans.pb(indd);
		for (int i=0; i<nww.size(); i++) ans.pb(nww[i]);
//	cout<<mx<<endl;
	return ans;
	
    
}
