#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

std::vector<int32_t> solve(std::vector<int32_t> A) {
    int n = A.size();
    vector<pair<int, int>> a{{0, 0}};
    for (int i = 0; i < n; i++) {
        a.push_back({A[i], i});
    }
    sort(a.begin(), a.end());
    int pref[n + 1];
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i].first;
    }
    int total = pref[n];
    int ub = (total + 1) / 2;
    int idx = lower_bound(pref + 1, pref + n + 1, ub) - pref;
    if (idx <= n / 2) {
        vector<int32_t> ans;
        for (int i = 1; i <= n; i++) {
            ans.push_back(a[i].second);
        }
        return ans;
    }
    set<pair<int, int>> free;
    for (int i = idx + 1; i <= n; i++) {
        free.insert(a[i]);
    }
    int l = 1, r = idx;
    while (idx > (n + 1) / 2) {
        int rem = idx - (n + 1) / 2;
        int lo = 1, hi = rem + 1;
        auto [val, id] = *free.rbegin();
        free.erase(--free.end());
        while (lo < hi) {
            int mid = (lo + hi + 1) / 2;
            if (pref[mid] <= val) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        idx -= lo;
        l += lo;
    }
    vector<int32_t> ans;
    int sum = 0;
    bool vis[n + 1];
    fill_n(vis, n + 1, false);
    for (int i = l; i <= r; i++) {
        ans.push_back(a[i].second);
        sum += a[i].first;
        vis[i] = true;
    }
    int i = n;
    while (sum < ub) {
        ans.push_back(a[i].second);
        sum += a[i].first;
        vis[i] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            ans.push_back(a[i].second);
        }
    }
    return ans;
}