#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

long long pref[200005];
pair<int, int> alt[200005];

vector<int> solve(vector<int> A){
    int n = A.size();
    for(int i=0;i<n;++i){alt[i].first=A[i]; alt[i].second=i;}

    sort(alt, alt+n);

    pref[0]=0;
    for(int i=0;i<n;++i) pref[i+1] = pref[i]+alt[i].first;

    long long t = (pref[n]/2) + (pref[n]%2);
    int amount = (n/2);
    
    int l=1, r=n-amount;
    while(l<=r){
        int mid = (l+r)/2;

        if(pref[amount-mid] + (pref[n]-pref[n-mid]) <= t) l=mid+1;
        else r=mid-1; 
    }

    int res=l;

    for(int i=0;i<(amount-res);++i){
        A[i] = alt[i].second;
    }
    for(int i=0;i<res;++i){
        A[amount-i-1] = alt[n-i-1].second;
    }
    for(int i=0;i<(amount-res);++i){
        A[i+amount] = alt[i+amount].second;
    }
    for(int i=0;i<res;++i){
        A[n-i-1] = alt[i+(amount-res)].second;
    }
    return A;
}
