#include "partition.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast","unroll-loops")
#pragma GCC target("avx2")
using namespace std;
using ll=long long;
#define f first
#define s second
void sert(const vector<pair<ll,ll>>::iterator& q,const vector<pair<ll,ll>>::iterator& w){//O(n)
    int n=w-q;
    if(n<=1)return;
    auto it=q+(n-1)/2;
    nth_element(q,it,w);
    sert(q+n/2,w);
}
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};
    sert(vec.begin(),vec.end());
    ll s=0;for(int i:A)s+=i;
    ll sum_half=0;for(int i=0;i<(n-1)/2;i++)sum_half+=vec[i].f;
    swap(vec[n-1],vec[(n-1)/2]);
    int ind=1;
    ll sum_halfi=sum_half+vec[(n-1)/2].f;
    while(ind <=(n-1)/2&&!(sum_half<(s+1)/2&&sum_halfi>=(s+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;
    for(auto i:vec)res.push_back(i.s);
    return res;
}
