#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;
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());
    ll s=0;
    for(int i=0; i<n; i++) s+=(ll)B[i].first;
    ll s1=0;
    for(int i=0; 2*i<n; i++) s1+=(ll)B[i].first;
    int k=0;
    while(s1*2<s){
        s1-=(ll)B[k].first;
        k++;
        s1+=(ll)B[n-k].first;
    }
    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;

}