#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
bool in[2000007];
///holy quickselect, spray and pray
vector<pair<int,int> >v;
vector<int>reord;
long long s;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
void select(int l,int r,long long sum)
{
    if(l==r)
    {
        reord.push_back(v[l].second);
        return;
    }
    int pivot=rng()%(r-l+1)+l;
    swap(v[pivot],v[r]);
    pivot=r;
    int il=l;
    long long sl=0;
    for(int i=r-1;i>=il;i--)
    {
        if(v[i].first>=v[pivot].first)
        {
            swap(v[i],v[pivot]);
            pivot=i;
        }
        else
        {
            while(il<=i && v[il].first<=v[pivot].first)
            {
                sl+=v[il].first;
                il++;
            }
            if(il>i)
            {
                break;
            }
            swap(v[il],v[i]);
            swap(v[i],v[pivot]);
            pivot=i;
        }
    }
    sl+=v[pivot].first;
    if(sl+sum<s)
    {
        for(int i=l;i<=pivot && reord.size()<(n+1)/2;i++)
        {
            reord.push_back(v[i].second);
        }
        if(reord.size()==(n+1)/2)
        {
            return;
        }
        select(pivot+1,r,sum+sl);
    }
    else
    {
        select(l,pivot,sum);
    }
}
std::vector<int> solve(std::vector<int> A) {
    n=A.size();
    v.clear();
    s=0;
    for(int i=0;i<A.size();i++)
    {
        v.push_back({A[i],i});
        in[i]=0;
        s+=A[i];
    }
    reord.clear();
    if(s%2==1)
    {
        s++;
    }
    s/=2;
    //cerr<<s;
    select(0,A.size()-1,0);
    vector<int>ans;
    if(reord.size()<(n+1)/2)
    {
        for(auto el:reord)
        {
            ans.push_back(el);
            in[el]=1;
        }
        for(int i=0;i<n;i++)
        {
            if(in[i])
            {
                ans.push_back(i);
            }
        }
        return ans;
    }
    int l=0,r=(n+1)/2-1;
    long long sum=0;
    for(int i=l;i<=r;i++)
    {
        sum+=v[i].first;
    }
    while(sum<s)
    {
        l++;
        r++;
        sum-=v[l-1].first;
        sum+=v[r].first;
    }
    for(int i=l;i<=r;i++)
    {
        ans.push_back(v[i].second);
        in[v[i].second]=1;
    }
    for(int i=0;i<A.size();i++)
    {
        if(!in[i])
        {
            ans.push_back(i);
        }
    }
    return ans;
}
