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