#include "bits/stdc++.h"
#include "partition.h"
// #include "grader.cpp"
using namespace std;

#define ll long long

ll n, ans, S, s;

vector <int> solve(vector<int> A) {
    n = (int)A.size();
    vector <int> a(n, 0);
    priority_queue <pair <ll,ll>> q;
    // vector <pair<ll,ll>> d;
    S = s = 0;
    for(int i = 0; i < n; i++) {
        // d.push_back({A[i],i});
        q.push({A[i], i});
        S += A[i];
    }
    for(int i = n - 1; i >= 0; i--) {
        if(i < n / 2) s += q.top().first;
        a[i] = q.top().second;
        q.pop();
    }
    // sort(d.begin(), d.end());
    // for(int i = 0; i < n; i++) {
    //     if(i < n / 2)s += d[i].first;
    //     a.emplace_back(d[i].second);
    // }
    int i = n - 1, j = max((n / 2) - 1, 0ll);
    while(s * 2 < S && i >= (n / 2) && j >= 0) {
        s -= A[a[j]];
        s += A[a[i]];
        swap(a[j], a[i]);
        i--;
        j--;
    }
    return a;
}