#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){
  if(k==n){
    long long sum=0;
    int i=0;
    while(i<n&&2*sum<S){
      sum+=A[sol[i]];
      i++;
    }

    int val=abs(2*i-n);
    // fprintf(stderr,"Am gasit o solutie cu valoarea %d:\n",val);
    // for(int i=0;i<n;i++){
    //   fprintf(stderr,"%d ",sol[i]);
    // }
    // fprintf(stderr,"\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);
        // fprintf(stderr,"La pasul %d aleg %d\n",k,i);
        bkt(k+1,A);
        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;
  }
  sol.clear();
  bestsol.clear();
  minval=n+1;
  bkt(0,A);

  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;
// }