#include<bits/stdc++.h>
#define endl "\n"
#include "partition.h"
using namespace std;
int n;
int pref[1000010];
int suff[1000010];
int binSearch(int x){
    int l=0,r = n,mid,ans = -1;
    while(l<=r){
        mid = (l+r)>>1;
        if(suff[mid]>=x){
            ans = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    return ans;
}
vector<int> solve(vector<int> A){
    n = A.size();
    vector<pair<int,int> > a(A.size());
    for(int i=0;i<A.size();i++){
        a[i] = {A[i],i};
    }
    sort(a.begin(),a.end());
    for(int i=n-1;i>=0;i--){
        suff[i] = suff[i+1] + a[i].first;
    }
    /*for(int i=0;i<n;i++){
        cout<<suff[i]<<" ";
    }
    cout<<endl;*/
    int S = suff[0];
    int sum = 0;
    int i = 0,idx;
    for(;i<n;i++){
        idx = binSearch(S/2-sum);
        //cout<<i<<" "<<idx<<" "<<n-2*idx+2*i<<endl;
        if(abs(n-2*idx+2*i)<=1) break;
        sum += a[i].first;
    }
    vector<int> ans;
    for(int ii=0;ii<i;ii++){
        ans.push_back(a[ii].second);
    }
    for(int ii=idx;ii<n;ii++){
        ans.push_back(a[ii].second);
    }
    for(int ii=i;ii<idx;ii++){
        ans.push_back(a[ii].second);
    }
    return ans;
}

/*int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<int> ans = solve(a);
    for(int i=0;i<n;i++){
        cout<<ans[i];
    }
    return 0;
}*/
