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

const long long MAXN = 2e6+7;
long long n;
pair<long long, long long> a[MAXN];
bool found[MAXN];

vector<int> solve(vector<int> A)
{
    n = A.size();
    fill(found, found+n+1, false);
    long long s = 0;
    for(long long i = 0; i < n; i++)
    {
        a[i+1] = {A[i], i};
        s += a[i+1].first;
    }
    sort(a+1, a+n+1);
    s = s/2+(s%2);
    long long sum = 0, nn = n/2+(n%2);
    vector<long long> ss;
    vector<pair<long long, long long> > ff;
    for(long long i = 1; i <= nn; i++)
    {
        sum += a[i].first;
        ff.push_back({a[i].second, i});
        found[a[i].second] = true;
    }
    for(long long i = n; i >= nn; i--)
    {
        if(sum >= s) break;
        sum += a[i].first-a[ff.back().second].first;
        found[ff.back().first] = false;
        ff.pop_back();
        ss.push_back(a[i].second);
        found[ss.back()] = true;
    }
    vector<int> ans;
    long long sz = ff.size();
    for(long long i = 0; i < sz; i++)
    {
        ans.push_back(ff[i].first);
    }
    sz = ss.size();
    for(long long i = 0; i < sz; i++)
    {
        ans.push_back(ss[i]);
    }
    for(long long i = 0; i < n; i++)
    {
        if(!found[i]) ans.push_back(i);
    }
    return ans;
}