#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void fill(int n, vector<int>& r,int k){
    vector<bool> exist(n,false);
    for(int i=0;i<=k;i++){
        exist[r[i]]=true;
    }
    int j=0;
    for(int i=k+1;i<n;i++){
        while(exist[j]) j++;
        r[i]=j;
        j++;
    }
}

vector<int> solve(vector<int> a){
    ll n = a.size();
    ll m = (n-1)/2;
    if(n==1) return {0};

    vector<pair<int,int>> b(n);
    for(int i=0;i<n;i++) b[i] = {a[i],i};
    sort(b.begin(),b.end());

    ll sum = 0;
    for(ll i=0;i<n;i++) sum += a[i];
    
    vector<int> res_bi(n,0);
    for(int i=0;i<m;i++){
        res_bi[i]=i;
    }
    res_bi[m]=n-1;

    ll curr_sum = 0;
    for(int i=0;i<=m;i++){
        curr_sum += b[res_bi[i]].first;
    }

    if(2*curr_sum>=sum){
        fill(n,res_bi,m);
        vector<int> res(n);
        for(int i=0;i<n;i++){
            res[i]=b[res_bi[i]].second;
        }
        return res;
    }
    int i;
    for(i=m-1;i>=0;i--){
        /*
        while(res_bi[i]<i+n-m-1){
            curr_sum+=b[res_bi[i]+1].first-b[res_bi[i]].first;
            res_bi[i]++;
            if(2*curr_sum>=sum){
                fill(n,res_bi,m);
                vector<int> res(n);
                for(int t=0;t<n;t++){
                    res[t]=b[res_bi[t]].second;
                }
                return res;
            }
        }*/

        if(2*(curr_sum+b[i+n-m-1].first-b[res_bi[i]].first)>=sum) break;
    }

    int minn = res_bi[i] , maxx = i+n-m-1;
    int midd = (minn+maxx)/2;
    while(midd>minn){
        if(2*(curr_sum+b[midd].first-b[res_bi[i]].first)>=sum){
            maxx = midd;
        } else {
            minn = midd;
        }
        midd = (minn+maxx)/2;
    }
    midd++;
    res_bi[i]=midd;

    fill(n,res_bi,m);
    vector<int> res(n);
    for(int t=0;t<n;t++){
        res[t]=b[res_bi[t]].second;
    }
    return res;
}
