#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));
            }
        }
    };


    vector<tuple<int, bool, int>> advPf;
    vector<tuple<int, bool, int>> advPfQ1;
    vector<tuple<int, bool, int>> advPfQ2;
    for (int i = 0; i <= n; ++i) {
        advPf.emplace_back(pf[i], true, i);
    }
    int sfSm = 0;
    for (int sf = 0; sf <= n; ++sf) {
        if (sf != 0) {
            sfSm += a[n - sf].first;
        }
        int ndMr = s - sfSm;
        advPfQ1.emplace_back(ndMr, false, sf);
        if (sfSm >= s) {
            break;
        }
    }
    reverse(advPfQ1.begin(), advPfQ1.end());
    for (int sf = 1; sf <= n; ++sf) {
        int st = n - sf;
        advPfQ2.emplace_back(s + pf[st], false, n + sf);
    }
    reverse(advPfQ2.begin(), advPfQ2.end());

    vector<tuple<int, bool, int>> megaPf(advPfQ1.size() + advPf.size());
    merge(advPfQ1.begin(), advPfQ1.end(), advPf.begin(), advPf.end(), megaPf.begin());
    vector<tuple<int, bool, int>> megaPf2(megaPf.size() + advPfQ2.size());
    merge(advPfQ2.begin(), advPfQ2.end(), megaPf.begin(), megaPf.end(), megaPf2.begin());

    vector<int> low_ans(2 * n + 10);
    // sort(advPf.begin(), advPf.end());
    vector<int> unknown;
    for (auto [vl, tp, i] : megaPf2) {
        if (tp) {
            for (int j : unknown) {
                low_ans[j] = i;
            }
            unknown.clear();
        } else {
            unknown.push_back(i);
        }
    }
    for (int j : unknown) {
        low_ans[j] = pf.size();
    }

    sfSm = 0;
    for (int sf = 0; sf <= n; ++sf) {
        if (sf != 0) {
            sfSm += a[n - sf].first;
        }
        int ndMr = s - sfSm;
        int more_lf = low_ans[sf];
        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;
        }
    }
    auto sum = [&](int l, int r) {
        return pf[r] - pf[l];
    };
    for (int sf = 1; sf <= n; ++sf) {
        int st = n - sf;
        int r = low_ans[n + sf] - st;
        int sm = sum(st, st + r);
        int first_get = r;
        // 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;
}
