#include<bits/stdc++.h>
#include "partition.h"

using namespace std;

vector<int> solve(vector<int>A)
{
    vector<pair<long long, long long>>v;

    long long sum=0;

    for (long long i=0; i<A.size(); i++)
    {
        v.push_back({A[i], i});
        sum+=A[i];
    }

    sum=sum/2+(sum%2);

    sort(v.begin(), v.end());

    long long ans=1e8;
    long long ansL;
    long long ansR;
    long long currsum=0;


    long long l=0;
    long long r=-1;

    while (1)
    {
        if (r==v.size()-1) break;
        //cout<<l<<" "<<r<<endl;
        r++;
        currsum+=v[r].first;

        while (currsum>=sum)
        {
            long long szl=r-l+1;
            long long szr=v.size()-szl;

            if (abs(szr-szl)<ans)
            {
                ans=abs(szr-szl);
                ansR=r;
                ansL=l;
            }

            currsum-=v[l].first;
            l++;
        }
    }

    vector<int>ret;

    for (long long i=ansL; i<=ansR; i++)
    {
        ret.push_back(v[i].second);
    }

    for (long long i=0; i<ansL; i++)
    {
        ret.push_back(v[i].second);
    }

    for (long long i=ansR+1; i<v.size(); i++)
    {
        ret.push_back(v[i].second);
    }
    //cout<<ans<<endl;
    return ret;
}

