#include <bits/stdc++.h>
#define int int64_t
using namespace std;

struct fenwick{
    int n;
    vector<int> a;
    fenwick(int _n){
        n = _n;
        a.assign(n+1, 0);
    }
    int sum(int i){
        int res = 0;
        while(i){
            res += a[i];
            i -= (i & -i);
        }
        return res;
    }
    void upd(int i, int j){
        while(i <= n){
            a[i] += j;
            i += (i & -i);
        }
    }
};

std::vector<int> solve(std::vector<int> A){
    int n = A.size();
    auto a = A;
    set<int> st;
    for(auto &i : a) st.insert(i);
    int sum = accumulate(a.begin(),a.end(),0LL);
    auto p = a;
    sort(p.begin(),p.end());
    int avg = p[((n-n%2)/2)];
    int subsm = 0, cnt = 0;
    map<int,int> mp, mt;
    while(subsm < ((sum+sum%2)/2)){
        auto t1 = st.lower_bound(avg);
        auto t2 = st.upper_bound(avg);
        int bst = 0;
        if(t2 == st.begin()){
            bst = *t1;
        } else if(t1 == st.end()){
            bst = *t2;
        } else{
            t2--;
            if(abs(*t1-avg) > abs(*t2-avg)){
                bst = *t2;
            } else{
                bst = *t1;
            }
        }
        mp[bst]++;
        mt[bst]++;
        subsm += bst;
        cnt++;
    }
    int cur = 0;
    auto b = a;
    for(int i = 0; i < a.size(); i++){
        if(mp[a[i]] > 0){
            b[i] = cur;
            mp[i]--;
            cur++;
        }
    }
    for(int i = 0; i < a.size(); i++){
        if(mt[a[i]] <= 0){
            b[i] = cur;
            cur++;
        }
    }
    int k = 0;
    return b;
    // cerr << cnt << " " << n-cnt << endl;
    // cerr << subsm << " " << sum-subsm << endl;
    // cerr << avg << endl << "---" << endl;
}

// signed main(){
//     cin.tie(0)->sync_with_stdio(0);
//     int _; cin >> _;
//     while(_--) solve();
// }