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

using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    vector<pair<int,int>>B;
    for(int i = 0; i < n; i ++)
        B.emplace_back(A[i],i);
    sort(begin(B),end(B));
    long long sm = 0;
    for (int i : A) sm += i;
    int bs=-1;
    for(int l=1,r=n/2;l<=r;){
        int i=(l+r)>>1;
        bool ok=true;
        long long smA = 0;
        for (int j = 0; j < i; j ++)
            smA+=B[j].first;
        if(smA-B[i-1].first>sm/2)
            ok=false;
        if(ok){
            bs=i,l=i+1;
        } else r=i-1;
    }
    if (bs==-1){
        vector<int>ans(n);
        iota(begin(ans),end(ans),0);
        return ans;
    }else{
        int i=bs;
        long long smA = 0;
        for (int j = 0; j < i; j ++)
            smA+=B[j].first;
        for(int j=i;j<n;j++){
            smA-=B[j-i].first;
            smA+=B[j].first;
            if(smA>sm/2){
                vector<int>ans;
                for(int k=j-i+1;k<=j;k++)
                    ans.push_back(B[k].second);
                for(int k=0;k<=j-i;k++)
                    ans.push_back(B[k].second);
                for(int k=j+1;k<n;k++)
                    ans.push_back(B[k].second);
                return ans;
            }
        }
        return {};
    }
}