#include "partition.h"
#include<bits/stdc++.h>
#pragma GGC optimize("fast-math,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
bool in[2000007];
vector<pair<int,int> >v;
long long s;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
long long ss=0;
int cnt=0;
void select(int &l,int &r)
{
    if(l==r)
    {
        cnt++;
        return;
    }
    int 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(ss+sl<s)
    {
        cnt+=pivot-l+1;
        if(cnt>(n+1)/2)
        {
            return;
        }
        ss+=sl;
        pivot++;
        select(pivot,r);
    }
    else
    {
        select(l,pivot);
    }
}
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];
    }
    if(s%2==1)
    {
        s++;
    }
    s/=2;
    ss=0;
    cnt=0;
    int l=0,r=n-1;
    select(l,r);
    vector<int>ans;
    if(cnt<(n+1)/2)
    {
        for(auto [_,idx]:v)
        {
            ans.push_back(idx);
        }
        return ans;
    }
    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;
}
