#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));
    vector<long long>P(n);
    long long sm = 0,sm2=B[0].first;
    for (int i : A) sm += i;
    int mx=sm2<sm/2?0:-1;
    for(int i =1;i<n/2;i++){
        sm2+=B[i].first;
        if(sm2<sm/2)mx=i;
        else break;
    }
    if(mx!=-1){
        int i=min(mx+1,n/2);
        long long smA=sm2;
        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;
            }
        }
    }
    vector<int>ans(n);
    iota(begin(ans),end(ans),0);
    return ans;
}