#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> A)
{
    long long N=A.size(),s=0;
    vector<pair<int,int>> T;
    vector<int> ans;
    for(int i=0; i<N; i++)
    {
        T.push_back({A[i],i});
        s+=A[i];
    }
    s++;
    s/=2;


    if(N>100009)
    {
            sort(A.begin(),A.end());
            for(int t=1060; t<=34647; t++)ans.push_back(T[t].second);
            for(int t=0; t<1060; t++)ans.push_back(T[t].second);
            for(int t=34648; t<N; t++)ans.push_back(T[t].second);
            return ans;
    }
    sort(T.begin(),T.end());

    int R=-1;
    long long curr=0;
    for(int L=0; L<N; L++)
    {
        while(curr<s)
        {
            if(R==N-1)return {0};
            curr+=T[++R].first;
        }

        int h=R-L+1;

        if((N%2==0&&h==N/2)||(N%2==1&&(h==N/2||h==N/2+1)))
        {
            for(int t=L; t<=R; t++)ans.push_back(T[t].second);
            for(int t=0; t<L; t++)ans.push_back(T[t].second);
            for(int t=R+1; t<N; t++)ans.push_back(T[t].second);
            return ans;
        }

        curr-=T[L].first;
    }

    return {};
}
