#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define f first
#define s second
std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<pair<ll,ll>> vec(n);for(int i=0;i<n;i++)vec[i]={A[i],i};
    nth_element(vec.begin(),vec.begin()+(n-1)/2,vec.end());
    ll sum=0;for(int i:A)sum+=i;
    ll sum_half=0;for(int i=0;i<(n-1)/2;i++)sum_half+=vec[i].f;
    swap(vec[max_element(vec.begin(),vec.end())-vec.begin()],vec[(n-1)/2]);
    int ind=1;
    ll sum_halfi=sum_half+vec[(n-1)/2].f;
    while(sum_halfi<(sum+1)/2){
        sum_half +=vec[n-1-ind].f - vec[(n-1)/2-ind].f;
        sum_halfi +=vec[n-1-ind].f - vec[(n-1)/2-ind].f;
        swap(vec[(n-1)/2-ind],vec[n-1-ind]);
        ind++;
    }
    vector<int> res(n);for(int i=0;i<n;i++)res[i]=vec[i].s;
    return res;
}
