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


#define N 3000005
#define ll long long

const int inf = INT_MAX;

ll n, ans, S = 0;
vector <int> a, b, c;
vector <pair<ll,ll>> d;

vector<int> solve(vector<int> A) {
    n = (int)A.size();
    d.clear();
    a.clear();
    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 / 2; i++) {
        s += d[i].first;
    }
    for(int i = 0; i < n; i++) {
        a.push_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;
}