#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#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;
    }
    int sfSm = 0;
    int it = pf.size();
    for (int sf = 0; sf <= n; ++sf) {
        if (sf != 0) {
            sfSm += a[n - sf].first;
        }
        int ndMr = s - sfSm;
        while (it > 0 && pf[it - 1] >= ndMr) {it--;}
        int more_lf = it;
        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];
    };
    it = pf.size();
    for (int sf = 1; sf <= n; ++sf) {
        int st = n - sf;
        while (it > 0 && pf[it - 1] >= s + pf[st]) {it--;}
        int r = it - 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);
    }
    return bestPerm;
}
