#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);
    mt19937 rng(time(0));
    l:
    shuffle(res.begin(),res.end(),rng);
    ll sum=0;for(int i:A)sum+=i;
    ll sum_half=0;for(int i=0;i<(n/2);i++)sum_half+=A[res[i]];
    swap(res[max_element(res.begin(),res.end(),[&](int a, int b){return A[a]<A[b];})-res.begin()],res[(n/2)]);
    int ind=1;
    ll sum_halfi=sum_half+A[res[(n/2)]];
    while(!(sum_half<(sum+1)/2&&sum_halfi>=(sum+1)/2)){
        if(ind>(n/2))goto l;
        sum_half +=A[res[n-1-ind]] - A[res[(n/2)-ind]];
        sum_halfi +=A[res[n-1-ind]] - A[res[(n/2)-ind]];
        swap(res[(n/2)-ind],res[n-1-ind]);
        ind++;
    }
    return res;
}