#include<vector>
#include<algorithm>
std::vector<int> solve(std::vector<int> A){
    std::vector<std::pair<int,int>>b(A.size());
    long long sm=0;
    int i,n=A.size();
    for(i=0;i<A.size();i++){
        b[i].first=A[i];
        b[i].second=i;
        sm+=A[i];
    }
    sort(b.begin(),b.end());
    long long cur=0;
    for(i=0;i<n;i++){
        cur+=b[i].first;
        if(cur>=((sm+1)>>1)){
            break;
        }
    }
    int ans=i+1-(n+1)/2;
    int l=0,r=n;
    std::pair<int,int>ans1={0,n};
    while(l!=i+1&&r!=i){
            ///cout<<l<<' '<<r<<endl;
        if(cur>=((sm+1)>>1)){
            ///cout<<cur<<endl;
            ///cout<<min(abs(i+1+n-r-l-(n+1)/2),abs(i+1+n-r-l-n/2))<<endl;
            if(ans>std::min(abs(i+1+n-r-l-((n+1)>>1)),abs(i+1+n-r-l-(n>>1)))){
                ans1={l,r};
                ans=std::min(abs(i+1+n-r-l-((n+1)>>1)),abs(i+1+n-r-l-(n>>1)));
                ///cout<<ans<<endl;
            }
            cur-=b[l].first;
            l++;
        }
        else{
            r--;
            cur+=b[r].first;
        }
    }
    std::vector<int>fans;
    int j=i;
    for(i=ans1.first;i<=j;i++){
        fans.push_back(b[i].second);
    }
    for(i=ans1.second;i<n;i++){
        fans.push_back(b[i].second);
    }
    for(i=ans1.second-1;i>j;i--){
        fans.push_back(b[i].second);
    }
    for(i=0;i<ans1.first;i++){
        fans.push_back(b[i].second);
    }
    return fans;
}
