#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<int> res(n);iota(res.begin(),res.end(),0);
    nth_element(res.begin(),res.begin()+(n-1)/2,res.end(),[&](int a, int b){return A[a]<A[b];});
    ll sum=0;for(int i:A)sum+=i;
    for(int i=0;i<(n-1)/2;i++)sum-=2*A[res[i]];
    swap(res[max_element(res.begin()+(n-1)/2,res.end(),[&](int a, int b){return A[a]<A[b];})-res.begin()],res[(n-1)/2]);
    int ind=1;
    while(A[res[(n-1)/2]]<(sum+1)/2){
        sum-=2*(A[res[n-1-ind]] - A[res[(n-1)/2-ind]]);
        swap(res[(n-1)/2-ind],res[n-1-ind]);
        ind++;
    }
    return res;
}