#include "partition.h"
#include "bits/stdc++.h"
using namespace std;

#define ll long long

vector<int>solve(vector<int>A)
{
      sort(A.begin(),A.end());
      ll n=(ll)A.size();
      ll sum=accumulate(A.begin(),A.end(),0ll);
      ll mn=n+100;
      for(int bit=0;bit<(1ll<<n);bit++){
            vector<int>aft;
            for(int i=0;i<n;i++){
                  if((1<<i)&bit) aft.push_back(i);
            }
            for(int i=0;i<n;i++){
                  if((1<<i)&bit) continue;
                  aft.push_back(i);
            }
            ll cur=0,cnt=0;
            for(int i=0;i<aft.size();i++){
                  cur+=A[aft[i]];
                  ++cnt;
                  if(cur>=(sum/2ll)+(sum&1ll)) break;
            }
            ll c2=n-cnt;
            mn=min(mn,abs(cnt-c2));
      }
      for(int bit=0;bit<(1ll<<n);bit++){
            vector<int>aft;
            for(int i=0;i<n;i++){
                  if((1<<i)&bit) aft.push_back(i);
            }
            for(int i=0;i<n;i++){
                  if((1<<i)&bit) continue;
                  aft.push_back(i);
            }
            ll cur=0,cnt=0;
            for(int i=0;i<aft.size();i++){
                  cur+=A[aft[i]];
                  ++cnt;
                  if(cur>=(sum/2ll)+(sum&1ll)) break;
            }
            ll c2=n-cnt;
            if(abs(cnt-c2)==mn){
                  return aft;
            }
      }
}
