#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};
    sort(vec.begin(),vec.end());
    ll s=0;for(int i:A)s+=i;
    ll sum_half=0;for(int i=0;i<n/2;i++)sum_half+=vec[i].f;
    swap(vec[n-1],vec[n/2]);
    int ind=1;
    ll sum_halfi=sum_half+vec[n/2].f;
    while(!(sum_half<s/2&&sum_halfi>=n/2)){
        swap(vec[n/2-ind],vec[n-1-ind]);
    }
    vector<int> res;
    for(auto i:vec)res.push_back(i.s);
    return res;
}
