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