 #include "partition.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
std::vector<int> solve(std::vector<int> A) {
    int n=A.size();
    vector<pair<int, int>> B(n);
    for(int i=0; i<n; i++) B[i]={A[i], i};
    sort(B.begin(), B.end());
    vl C(n+1);
    for(int i=0; i<n; i++) C[i+1]=C[i]+(ll)B[i].first;
    ll s=C[n];
    ll s1=C[(n+1)/2];    
    int a=-1;
    int b=n;
    while(a+1<b){
        int c=(a+b)/2;
        if(2*(s1+s-C[n-c]-C[c])<s){
            a=c;
        }
        else b=c;
    }
    int k=b;
    vi ans(n);
    for(int i=k; i<=(n-1)/2; i++) ans[i-k]=B[i].second;
    for(int i=0; i<k; i++) ans[i+(n+1)/2-k]=B[n-i-1].second;
    for(int i=0; i<k; i++) ans[i+(n+1)/2]=B[i].second;
    for(int i=0; i<n-(n+1)/2-k; i++) ans[i+(n+1)/2+k]=B[i+(n+1)/2].second;
    return ans;

}
