#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
// #define int long long
using ll = long long;

constexpr int MAXN = 2000000;
int order[MAXN];
ll pf[MAXN + 1];

vector<signed> solve(vector<signed> AA) {
    int n = AA.size();
    iota(order, order + n, 0);
    sort(order, order + n, [&](int i, int j) {
        return AA[i] < AA[j];
    });
    ll s = 0;
    for (int i = 0; i < n; ++i) {
        s += AA[i];
    }
    s = (s + 1) / 2;
    int bstDf = 1000000000, bstSf = -1;
    pf[0] = 0;
    for (int i = 0; i < n; ++i) {
        pf[i + 1] = pf[i] + AA[order[i]];
    }
    ll sfSm = 0;
    for (int sf = 0; sf <= n; ++sf) {
        if (sf != 0) {
            sfSm += AA[order[n - sf]];
        }
        if (sfSm >= s) {
            break;
        }
    }
    auto sum = [&](int l, int r) {
        return pf[r] - pf[l];
    };
    int it = n + 1;
    int it2 = n + 1;
    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;
        ll 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) {
            ll ndMr = s - sm;
            while (it2 > 0 && pf[it2 - 1] >= ndMr) {it2--;}
            int more_lf = it;
            int first_get2 = more_lf + sf;
            if (abs(first_get2 - (n - first_get2)) < bstDf) {
                bstDf = abs(first_get2 - (n - first_get2));
                bstSf = sf;
            }
        } else {
            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(order[n - bstSf + i]);
    }
    for (int i = 0; i < n - bstSf; ++i) {
        bestPerm.push_back(order[i]);
    }
    return bestPerm;
}
