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

#define MAXN 2000000

int v[MAXN];
long long S;


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

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

  sol.clear();
  bestsol.clear();
  minval=n/4;
  found=false;
  bkt(0,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;
}
