#include "partition.h"
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
std::vector<int> solve(std::vector<int> A)
{
    vector<pair<long long,long long>>order;

    long long n=A.size();
    long long sum=0;
    for(long long i=0;i<A.size();i++)
    {
        sum+=A[i];
        order.push_back({A[i],i});
    }
    sort(order.begin(),order.end());

    long long best=n;
    vector<int>curans,other,ans;
    for(long long mask=1;mask<(1<<n);mask++)
    {
        long long f=-1;
        long long cursum=0,sz=0;
        bool ok=1;
        long long cnt=0;
        curans.clear();
        other.clear();
        for(long long i=0;i<n;i++)
        {
            if(((1<<i)&(mask))==0){other.push_back(order[i].second);continue;}
            curans.push_back(order[i].second);
            sz++;
            cursum+=order[i].first;

            if(cursum*2LL>=sum)
            {
                cnt++;
            }
        }

        if(cnt==1)
        {
            if(abs(sz-(n-sz))<best)
            {
                best=abs(sz-(n-sz));
                for(long long x:other)curans.push_back(x);
                ans=curans;
            }
        }
    }

    return ans;
}
