#include<bits/stdc++.h>
#include "partition.h"
#define endl '\n'
#define X first
#define Y second
using namespace std;
const long long maxn=2e3+10;
map<long long,pair<long long,bool>> mp[maxn];
map<long long,vector<int>> last[maxn];
long long a[maxn];
bool used[maxn];
std::vector<int> solve(std::vector<int> A)
{
    vector<int> ans;
    long long n=A.size();
    long long sum=0;
    for(long long i=0; i<n; i++)
    {
        a[i+1]=A[i];
        sum+=a[i+1];
    }
    for(long long i=0;i<=n;i++)
    {
        mp[i].clear();
        last[i].clear();
        used[i]=0;
    }
    mp[0][0]={0,1};
    last[0][0]={};
    for(long long i=1; i<=n; i++)
    {
        mp[i]=mp[i-1];
        last[i]=last[i-1];
        for(auto [key,value]:mp[i-1])
        {
            if(value.Y==1)
            {
                if(mp[i][key+a[i]].Y==0)
                {
                    mp[i][key+a[i]]= {value.X+1,1};
                    last[i][key+a[i]]=last[i-1][key];
                    last[i][key+a[i]].push_back(i);
                }
                else
                {
                    if(abs(n-2*mp[i][key+a[i]].X)>abs(n-2*(value.X+1)))
                    {
                        mp[i][key+a[i]]= {value.X+1,1};
                        last[i][key+a[i]]=last[i-1][key];
                        last[i][key+a[i]].push_back(i);
                    }
                }
            }
        }
    }
    for(auto [key,value]:mp[n])
    {
        if(key>=(sum/2+sum%2))
        {
            ans=last[n][key];
            break;
        }
    }
    for(auto i:ans)
    {
        used[i]=1;
    }
    for(long long i=1;i<=n;i++)
    {
        if(used[i]==0)
        {
            ans.push_back(i);
        }
    }
    for(long long i=0;i<ans.size();i++)
    {
        ans[i]--;
    }
    return ans;
}
