#include <bits/stdc++.h>

using namespace std;
using ll = long long;

mt19937 rng(5125123);

vector<int> solve(vector<int> A) {
    int n = A.size();
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    // sort(ord.begin(), ord.end(), [&](int x, int y) {
    //     return A[x] < A[y];
    // });
    shuffle(ord.begin(), ord.end(), rng);
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += A[i];
    }
    vector<ll> pref(n);
    for (int i = 0; i < n; ++i) {
        pref[i] = (i == 0 ? 0 : pref[i - 1]) + A[ord[i]];
    }
    auto get_sum = [&](int l, int r) {
        if (l == 0) return pref[r];
        return pref[r] - pref[l - 1];
    };
    int pA = n, pB = 0;
    int ans = 1e9;
    vector<int> sol;
    int whol, whor;
    int r = 0;
    for (int l = 0; l < n; ++l) {
        while (r < n && get_sum(l, r) < (sum + 1) / 2) ++r;
        if (r == n) continue;
        ll s = get_sum(l, r);
        int x = r - l + 1;
        int y = n - x;
        if (s >= (sum + 1) / 2) {
            if (ans > abs(x - y)) {
                ans = abs(x - y);
                whol = l;
                whor = r;
                // sol.clear();
                // for (int k = l; k <= r; ++k) {
                //     sol.push_back(ord[k]);
                // }
            }
        }
        if (ans == 0) break;
    }
    for (int i = whol; i <= whor; ++i) sol.push_back(ord[i]);
    // cout << "! " << ans << "\n";
    vector<int> taken(n);
    for (auto x : sol) taken[x] = 1;
    for (int i = 0; i < n; ++i) if (!taken[i]) sol.push_back(i);
    return sol;
}