#include "partition.h"
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;

struct st_aux{
    long long a,ind;
};

#pragma GCC optimize "unroll-loops","O3"
#pragma GCC target "avx2"

vector<st_aux> aux;

bool cmp(st_aux a,st_aux b){
    return a.a<b.a;
}

vector<int> solve(vector<int> A) {
    long long min1=1e18,mask=0,bit,i,auxmin1,cnt,sum=0,sumcur,n;
    aux.clear();n=A.size();
    for(auto it:A) sum+=it;
    ///cout<<sum<<" ||\n";
    for(bit=0;bit<(1<<n);bit++){
        auxmin1=cnt=0;sumcur=0;
        for(i=0;i<n;i++){
            if(bit&(1<<i)){
                sumcur+=A[i];
                auxmin1=max(auxmin1,1ll*A[i]);
                cnt++;
            }
        }
        ////cout<<bit<<": "<<sumcur<<" "<<sumcur-auxmin1<<" "<<max((((int)A.size()-cnt)-cnt),cnt-(((int)A.size()-cnt)))<<"|\n";
        if(2*(sumcur-auxmin1)<sum && 2*sumcur>=sum && max((((int)n-cnt)-cnt),cnt-(((int)n-cnt)))<min1){
            mask=bit;
            min1=max((((int)n-cnt)-cnt),cnt-(((int)n-cnt)));
        }
        if(!min1) break;
    }
    ///cout<<"| "<<mask<<"| ";
    for(i=0;i<n;i++){
        if((1<<i)&mask){
            aux.push_back({A[i],i});
        }
    }
    vector<int> rasp;rasp.clear();
    sort(aux.begin(),aux.end(),cmp);
    for(auto it:aux) rasp.push_back(it.ind);
    for(i=0;i<n;i++){
        if((1<<i)&mask) continue;
        rasp.push_back(i);
    }
    return rasp;
}
