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

struct st_aux{
    long long a,ind;
};

vector<st_aux> aux;
vector<long long> a;

bool cmp(st_aux a,st_aux b){
    return a.a<b.a;
}
long long sum,mint,mask;

void back_track(long long poz,long long sumcur,long long min1,long long cnt,long long bit){
    if(poz==a.size()){
        if(2ll*(sumcur-min1)<sum && 2ll*sumcur>=sum && max((((long long)a.size()-cnt)-cnt),cnt-(((long long)a.size()-cnt)))<mint){
            ///printf("a");
            mask=bit;
            mint=max((((long long)a.size()-cnt)-cnt),cnt-(((long long)a.size()-cnt)));
        }
        return;
    }
    back_track(poz+1,sumcur,min1,cnt,bit);
    sumcur+=a[poz];min1=min(min1,(long long)a[poz]);cnt++;
    bit+=((1ll)<<poz);
    back_track(poz+1,sumcur,min1,cnt,bit);
}

vector<int> solve(vector<int> A) {
    long long bit,i,auxmin1,cnt;
    mint=1e18;sum=mask=0;
    aux.clear();a.clear();
    for(auto it:A){
        a.push_back(1ll*it);
    }
    for(auto it:A) sum+=1ll*it;
    back_track(0,0,1e9,0,0);
    for(i=0;i<A.size();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<A.size();i++){
        if((1<<i)&mask) continue;
        rasp.push_back(i);
    }
    return rasp;
}
