#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#include "partition.h"
using namespace std;
const int maxn = 2e3+10;
int n;
bool used[maxn];
vector<int> solve(vector<int> A)
{
    n=A.size();
    vector<pair<int,int>> a;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        a.push_back({A[i],i});
        sum+=A[i];
    }
    sort(a.rbegin(),a.rend());
    ll best=INT_MAX;
    int idx=-1;
    ll goal=(sum+1)/2;
    for(int i=0;i<n;i++)
    {
        ll curr=0;
        int cntr=0;
        for(int j=i;j<n;j++)
        {
            if(curr+a[i].f<goal) {curr+=a[i].f;cntr++;}
        }
        if(best>abs(cntr+1-abs(n-cntr-1)))
        {
            best=abs(cntr+1-abs(n-cntr-1));
            idx=i;
        }
    }
    vector<int> idxs;
    int curr=0;
    for(int i=idx;i<n;i++)
    {
        if(curr+a[i].f<goal)
        {
            curr+=a[i].f;
            idxs.push_back(a[i].s);
            used[a[i].s]=1;
        }
    }
    for(int i=0;i<n;i++) if(!used[i]) idxs.push_back(i);
    return idxs;
}
