#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<pair<int,int>> a(n);
    for(int i=0;i<n;i++)a[i]={A[i],i};
    long long as=0;
    for(int i=0;i<n;i++)as+=a[i].first;
    sort(a.begin(),a.end());
    vector<pair<int,int>> ca=a;
    vector<int> ans(n);
    long long sm=0;
    int p=((1+n)/2)-1;
    for(int i=0;i<=p;i++){
        sm+=ca[i].first;
        a[i]=ca[p-i];
    }
    int o=p;
    int j=n-1;
    while(sm<(as+1)/2){
        sm+=a[j].first-a[o].first;
        swap(a[o],a[j]);
        o--;
        j--;
        if(o==-1 or j==p)break;
    }
    for(int i=0;i<n;i++)ans[i]=a[i].second;
    return ans;
}