#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
long long s=0,sum=0,mn=1e18;
pair <int,int> a[2*1048576];
int n,p[30],used[2*1048576],pf[2*1048576];
vector <int> ans;
void print()
{
    vector <int> v;
    v.clear();
    long long br=0,sum1=0,s1=0;
    for(long long i=0; i<n; i++)
    {
        if(p[i]==1)
        {
            sum1+=a[i].first;
            br++;
            if(sum1>=s/2+s%2)
            {
                if(mn>abs(br-(n-br)))
                {
                    mn=abs(br-(n-br));
                    ans.clear();
                    for(int j=0;j<=i;j++)
                    {
                        if(p[j]==1)ans.push_back(a[j].second);
                    }
                }
                return;
            }
        }
    }
}
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;
    n=A.size();
    for(long long i=0; i<n; i++)
    {
        a[i]={A[i],i};
        s+=a[i].first;
        used[i]=0;
        p[i]=0;
    }
    sort(a,a+n);
    pf[0]=a[0].first;
    for(int i=1;i<n;i++)
    {
        pf[i]=pf[i-1]+a[i].first;
    }
    int mode=0;
    ans.resize(n);
    int p1=0,p2=n-1,sum=0;
    for(int i=n-1;i>=0;i--)
    {
        if((n-i)%2==1)
        {
            if(i>0&&(sum+(a[i].first-a[i-1].first))>=pf[i-1])
            {
                while(p1<=p2)
                {
                    ans[p1++]=a[i].second;
                    i--;
                }
                return ans;
            }
            ans[p2--]=a[i].second;
            if(i>0)
            sum+=a[i].first-a[i-1].first;
        }
        else
        {
            ans[p1++]=a[i].second;
        }
    }
    return ans;
}
