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

constexpr int MAXN = 2000000;
int order[MAXN];
ll pf[MAXN + 1];
mt19937 rndgen(228228228);

vector<signed> solve(vector<signed> AA) {
    int n = AA.size();
    ll s = 0;
    for (int i = 0; i < n; ++i) {
        s += AA[i];
    }
    s = (s + 1) / 2;
    vector<vector<int>> z(30);
    for (int i = 0; i < n; ++i) {
        z[__lg(AA[i])].push_back(i);
    }
    int ind = 0;
    for (auto &v : z) {
        for (int i : v) {
            order[ind++] = i;
        }
    }
    // iota(order, order + n, 0);
    // sort(order, order + n, [&](int i, int j) {
    //     return AA[i] < AA[j];
    // });
    int bstDf = 1000000000, bstSf = -1;
    pf[0] = 0;
    for (int i = 0; i < n; ++i) {
        pf[i + 1] = pf[i] + AA[order[i]];
    }
    auto sum = [&](int l, int r) {
        return pf[r] - pf[l];
    };
    int it = 0;
    int it2 = 0;
    for (int sf = n; sf >= 1; --sf) {
        int st = n - sf;
        if (sum(st, n) < s) {
            ll ndMr = s - sum(st, n);
            while (it2 < n + 1 && pf[it2] < 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;
                if (bstDf <= 1) break;
            }
        } else {
            while (it < n + 1 && pf[it] < s + pf[st]) {it++;}
            int r = it - st;
            ll sm = sum(st, st + r);
            int first_get = r;
            if (abs(first_get - (n - first_get)) < bstDf) {
                bstDf = abs(first_get - (n - first_get));
                bstSf = sf;
                if (bstDf <= 1) break;
            }
        }
    }
    vector<signed> bestPerm;
    bestPerm.reserve(n);
    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]);
    }
    cerr << bstDf << "\n";
    return bestPerm;
}
