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

vector<signed> solve(vector<signed> AA) {
    int n = AA.size();
    vector<pair<int, int>> a(n);
    int s = 0;
    for (int i = 0; i < n; ++i) {
        a[i] = {AA[i], i};
        s += a[i].first;
    }
    s = (s + 1) / 2;
    sort(a.begin(), a.end());
    int bstDf = 1000000000, bstSf = -1;
    vector<int> pf(n + 1);
    for (int i = 0; i < n; ++i) {
        pf[i + 1] = pf[i] + a[i].first;
    }
    auto rate = [&](const vector<signed> &prm) {
        int sm = 0;
        for (int i = 0; i < n; ++i) {
            sm += AA[prm[i]];
            if (sm >= s) {
                return abs((n - i - 1) - (i + 1));
            }
        }
    };
    int sfSm = 0;
    for (int sf = 0; sf <= n; ++sf) {
        if (sf != 0) {
            sfSm += a[n - sf].first;
        }
        int ndMr = s - sfSm;
        int more_lf = lower_bound(pf.begin(), pf.end(), ndMr) - pf.begin();
        int first_get = more_lf + sf;
        if (abs(first_get - (n - first_get)) < bstDf) {
            bstDf = abs(first_get - (n - first_get));
            bstSf = sf;
        }
        if (sfSm >= s) {
            break;
        }
    }
    for (int sf = 1; sf <= n; ++sf) {
        int st = n - sf;
        int sm = 0, first_get = 0;
        for (int i = st; i < n; ++i) {
            sm += a[i].first;
            first_get++;
            if (sm >= s) {
                break;
            }
        }
        if (sm < s) {
            continue;
        }
        if (abs(first_get - (n - first_get)) < bstDf) {
            bstDf = abs(first_get - (n - first_get));
            bstSf = sf;
        }
    }
    vector<signed> bestPerm;
    for (int i = 0; i < bstSf; ++i) {
        bestPerm.push_back(a[n - bstSf + i].second);
    }
    for (int i = 0; i < n - bstSf; ++i) {
        bestPerm.push_back(a[i].second);
    }
    assert(rate(bestPerm) == bstDf);
    return bestPerm;
}
