#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#include "partition.h"
using namespace std;
const int maxn = 2e6+10;
int n;
bool used[maxn];
vector<int> solve(vector<int> A)
{
    n=A.size();
    vector<pair<int,int>> a;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        a.push_back({A[i],i});
        sum+=A[i];
    }
    ll goal=(sum+1)/2;
    sort(a.begin(),a.end());
    int bestmask=-1;
    int currbest=INT_MAX;
    for(int i=0;i<(1<<n);i++)
    {
        vector<int> id;
        for(int j=0;j<n;j++)
        {
            if(i&(1<<j)) id.push_back(j);
        }
        int cntr=0;
        int curr=0;
        bool fl=0;
        for(int i=0;i<id.size();i++)
        {
            curr+=a[id[i]].f;
            cntr++;
            if(curr>=goal) {fl=1;break;}
        }
        if(!fl) continue;
        if(currbest>abs(cntr-(n-cntr)))
        {
            bestmask=i;
            currbest=abs(cntr-(n-cntr));
        }
    }
    vector<int> idxs;
    for(int i=0;i<n;i++)
    {
        if(bestmask&(1<<i)) idxs.push_back(a[i].s);
    }
    for(int i=0;i<n;i++)
    {
        if(bestmask&(1<<i)) continue;
        idxs.push_back(a[i].s);
    }
    return idxs;
}
