#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
bool in[2000007];
std::vector<int> solve(std::vector<int> A) {
    vector<pair<int,int> >v;
    long long s=0;
    for(int i=0;i<A.size();i++)
    {
        v.push_back({A[i],i});
        in[i]=0;
        s+=A[i];
    }
    if(s%2==1)
    {
        s++;
    }
    sort(v.begin(),v.end());
    queue<int>q;
    vector<int>ans;
    long long curr=0;
    for(int i=0;i<(A.size()+1)/2;i++)
    {
        curr+=v[i].first;
        if(curr>=s/2)
        {
            for(auto [_,el]:v)
            {
                ans.push_back(el);
            }
            return ans;
        }
        q.push(v[i].second);
    }
    int lst=A.size()-1;
    while(curr<s/2)
    {
        curr-=A[q.front()];
        q.pop();
        q.push(v[lst].second);
        curr+=v[lst].first;
        lst--;
    }
    while(!q.empty())
    {
        ans.push_back(q.front());
        in[q.front()]=1;
        q.pop();
    }
    for(int i=0;i<A.size();i++)
    {
        if(!in[i])
        {
            ans.push_back(i);
        }
    }
    return ans;
}
