#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
long long s=0,sum=0,mn=1e18,a[2*1048576],n,p[30],used[2*1048576];
pair <long long,long long> x;
vector <int> ans;
void print()
{
    vector <int> v;
    vector <long long> v1;
    v.clear();
    v1.clear();
    long long br=0,sum1=0,s1=0;
    for(long long i=0;i<n;i++)
    {
        if(p[i]==1)
        {
            sum1+=a[i];
            v1.push_back(sum1);
            v.push_back(i);
            br++;
        }
    }
    if((v1.size()==1&&v1[0]>=s/2+s%2)||(v1.size()>=2&&v1[v1.size()-2]<s/2+s%2&&v1.back()>=s/2+s%2))
    {
        if(mn>abs(br-(n-br)))
        {
            mn=abs(br-(n-br));
            ans=v;
        }
    }
}
void rek(long long pos)
{
    for(long long i=0;i<2;i++)
    {
        p[pos]=i;
        if(pos==n-1)print();
        else rek(pos+1);
    }
}
vector<int> solve(vector<int> A)
{
    mn=1e18;
    s=0;
    sum=0;
    n=A.size();
    for(long long i=0;i<n;i++)
    {
        a[i]=A[i];
        s+=a[i];
        used[i]=0;
        p[i]=0;
    }
    sort(a,a+n);
    rek(0);
    for(auto i:ans)used[i]=1;
    for(long long i=0;i<n;i++)
    {
        if(!used[i])ans.push_back(i);
    }
    return ans;
}
