#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e6 + 10;
//vector < pair < int, int > > g;
long long total = 0;
int n, used[maxn];
std::vector<int> solve(std::vector<int> A)
{

    n = A.size();


    //g.clear();
    vector < pair < int, int > > g;
    for (int i = 0; i < n; ++ i)
    {
        g.pb(make_pair(A[i], i));
    }
    sort(g.begin(), g.end());
    vector < int > ans;
    total = 0;
    for (int i = 0; i < n; ++ i)
        total += A[i];

    int mindif = n+1;
    //vector < int > ans;
    ans.pb(0);
    for (int pref = 0; pref < n; ++ pref)
    {
        for (int suff = n-1; suff > pref; -- suff)
        {
            long long sum = 0, invalid = 0;
            int cntis = 0, cntisnt = n;
            for (int i = 0; i <= pref && !invalid; ++ i)
            {
                if(sum * 2 >= total)invalid = 1;
                sum += g[i].first;
                cntis ++;
                cntisnt --;
            }
            for (int i = suff; i < n && !invalid; ++ i)
            {
                if(sum * 2 >= total)invalid = 1;
                sum += g[i].first;
                cntis ++;
                cntisnt --;
            }
            if(!invalid)
            {
                //cout << cntis << "  " << cntisnt << endl;
                if(abs(cntis - cntisnt) < mindif)
                {
                    mindif = abs(cntis - cntisnt);
                    vector < int > curr;
                    for (int i = 0 ; i <= pref; ++ i)
                        curr.pb(g[i].second);
                    for (int i = suff; i < n; ++ i)
                        curr.pb(g[i].second);
                    for (int i = pref + 1; i < suff; ++ i)
                        curr.pb(g[i].second);
                    ans = curr;
                }
            }
        }
    }
   // cout << mindif << endl;
    return ans;
}
