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

#define ll long long

ll n, ans, S = 0;

vector <int> solve(vector<int> A) {
    n = (int)A.size();
    vector <int> a;
    vector <pair<ll,ll>> d;
    S = 0;
    for(int i = 0; i < n; i++) {
        d.push_back({A[i],i});
        S += A[i];
    }
    sort(d.begin(), d.end());
    ll s = 0;
    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 -= d[j].first;
        s += d[i].first;
        swap(a[j], a[i]);
        i--;
        j--;
    }
    return a;
}