#include<bits/stdc++.h>
#include "partition.h"
using namespace std;
const long long maxn=1e6;
map<long long,vector<long long> >m[2];
long long n=0;
bool used[maxn];
std::vector<int> solve(std::vector<int> A)
{
    n=A.size();
    vector<int>ans;
    vector<long long>a;
    m[0].clear();
    m[1].clear();
    a.clear();
    ans.clear();
    long long s=0;
    for(long long i=0;i<n;i++)
    {
        s+=A[i];
        a.push_back(A[i]);
    }
    if(s%2)++s;
    s/=2;
    //cout<<s<<endl;
    long long h=0;
    for(long long i=0;i<n;i++)
    {
        h=i%2;
        //cout<<h<<endl;
        if(i==0)
        {
            m[0][a[0]].push_back(0);
            continue;
        }
        bool l=1;
        for(auto& j:m[h^1])
        {
            long long st=j.first;
            //cout<<st<<" sere mi se "<<i<<" "<<j.second.size()<<endl;
            if(st>=s)l=0;
            m[h][st]=j.second;
            if(l)m[h][st+a[i]]=j.second;
            if(l)m[h][st+a[i]].push_back(i);
        }
        if(m[h][a[i]].empty())m[h][a[i]].push_back(i);
    }
    h=(n-1)%2;
    int hh=n;
    if(n%2)hh++;
    //cout<<n<<" niga"<<endl;
    for(auto& i:m[h])
    {
        if(i.first<s)continue;
        long long sz1=ans.size();
        long long sz2=i.second.size();
        //cout<<i.first<<" sere mi se "<<sz1<<" "<<sz2<<endl;
        //cout<<abs(n-2*sz2)<<" a "<<endl;
        if(abs(hh-2*sz1)>abs(hh-2*sz2))
        {
            ans.clear();
            memset(used,0,sizeof(used));
            for(long long& z:i.second)
            {
                //cout<<z<<endl;
                ans.push_back(z);
                used[z]=1;
            }
        }
    }
    for(long long i=0;i<n;i++)
    {
        if(!used[i])ans.push_back(i);
    }
    return ans;
}
