#include "partition.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> solve(vector<int> A){
    vector<pair<int,int> >B;
    for(int i=0;i<A.size();i++){
        B.push_back({A[i],i});
    }
    sort(B.begin(),B.end());
    ll n=A.size();
    ll sum=0;
    for(ll i:A) sum+=i;
    ll thr=(sum+1)/2;
    ll ans=n+1,ansnum=0;
    vector<int>anss;
    for(ll i=0;i<(1<<n);i++){
        ll sm=0,cnt=0;
        bool is=1;
        vector<pair<int,int> >vv;
        for(ll j=0;j<n;j++){
            if(i&(1<<j)){
                if(sm>=thr){
                    is=false;
                    break;
                }
                sm+=B[j].first;
                cnt++;
            }
        }
        if(is==0) continue;
        if(sm>=thr){
            if(abs(n-ans-ans)>abs(n-cnt-cnt)){
                // cout<<i<<' '<<sm<<' '<<thr<<' '<<abs(n-ans-ans)<<' '<<abs(n-cnt-cnt)<<endl;
                ans=cnt;
                ansnum=i;
                if(abs(n-ans-ans)<=1) break;
            }
        }
    }
    anss.clear();
    for(ll j=0;j<n;j++){
        if(ansnum&(1<<j)){
            anss.push_back(B[j].second);
        }
    }
    for(ll j=0;j<n;j++){
        if(!(ansnum&(1<<j))){
            anss.push_back(B[j].second);
        }
    }
    return anss;
}