#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
std::vector<int> solve(std::vector<int> A) {
    ll n=A.size();
    ll s=0;
    for(int i=0;i<n;i++)
    {
        s+=A[i];
    }
    ll x=(s+1)/2;
    pair<ll,ll>cur={n+1,s};
    vector<int>b;
    vector<bool>y(n);
    for(int i=0;i<(1<<n);i++)
    {
        ll c=0,r=0;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j))
            {
                if(c>=x)
                    break;
                c+=A[j];
                r++;
            }
        }
        if(c>=x)
        {
            ll gh=abs(r-(n-r));
            pair<ll,ll>f={gh,c};
            if(f<cur)
            {
                b.clear();
                y.clear();
                ll u=0;
                for(int j=0;j<n;j++)
                {
                    if(u==r)
                        break;
                    if(i&(1<<j))
                    {
                        u++;
                        b.push_back(j);
                    }
                }
                cur=f;
            }
        }
    }
    for(int i:b)
        y[i]=1;
    for(int i=0;i<n;i++)
    {
        if(!y[i])
        b.push_back(i);
    }
    return b;
}
