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

#define MAXN 2000000

int ind[MAXN];
long long S;

vector<int> sol,bestsol;
bool used[MAXN];
int n,minval;
void bkt(int k,vector<int> A,long long sum,int cnt){
  if(minval==0||(n%2==1&&minval==1)){
    return;
  }

  if(k==(n+1)/2+1){
    int val=abs(2*cnt-n);
    if(val<minval){
      minval=val;
      bestsol=sol;
    }
  }else{
    for(int i=0;i<n;i++){
      if(!used[i]){
        used[i]=true;
        sol.push_back(i);
        bkt(k+1,A,sum+(2*sum<S?A[i]:0),cnt+(2*sum<S?1:0));
        used[i]=false;
        sol.pop_back();
      }
    }
  }
}

vector<int> solve(vector<int> A){
  n=A.size();
  int i;

  S=0;
  for(i=0;i<n;i++){
    S+=A[i];
    used[i]=false;
  }

  sort(A.begin(),A.end(),[](int a,int b){
    return a>b;
  });

  sol.clear();
  bestsol.clear();
  minval=n+1;
  bkt(0,A,0LL,0);

  for(int val:bestsol){
    used[val]=true;
  }

  for(i=0;i<n;i++){
    if(!used[i]){
      bestsol.push_back(i);
    }
  }

  // fprintf(stderr,"%d\n",minval);

  return bestsol;
}

// vector<int> solve(vector<int> A){
//   int n=A.size();
//   int i;
//   vector<int> sol;

//   for(i=0;i<n;i++){
//     ind[i]=i;
//   }

//   sort(ind,ind+n,[&](int a,int b){
//     return A[a]<A[b];
//   });

//   for(i=0;i<(n+1)/2-1;i++){
//     sol.push_back(ind[i]);
//   }
//   sol.push_back(ind[n-1]);
//   for(i=(n+1)/2-1;i<n-1;i++){
//     sol.push_back(ind[i]);
//   }

//   return sol;
// }