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