#include "partition.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll getSum(const vector<int>& v, const vector<int>& idx, int l, int r) {
    ll ans = 0;
    for (int i = l; i <= r; i++) { ans += v[idx[i]]; }
    return ans;
}

vector<int> solve(vector<int> A) {
    int n = A.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [A](int i1, int i2) { return A[i1] < A[i2]; });
    ll S = getSum(A, idx, 0, n - 1), sum = getSum(A, idx, 0, (n - 1) / 2);
    int i = 0;
    while (sum * 2 < S) {
        assert(i < n / 2 + 3);
        sum += A[idx[n - 1 - i]] - A[idx[i]];
        swap(idx[i], idx[n - 1 - i]);
        i++;
    }
    reverse(idx.begin(), idx.begin() + (n - 1) / 2 + 1);
    return idx;
}
