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

#define ll long long

ll INF = 1e17;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    int goal = (n + 1) / 2;
    vector<pair<ll, int>> curr;
    ll s = 0;
    for (int i = 0; i < n; i++) {
        curr.push_back({A[i], i});
        s += A[i];
    }
    sort(curr.begin(), curr.end());
    ll currS = 0, targ = (s + 1) / 2;
    int ptr;
    for (int i = 0; i < n; i++) {
        currS += curr[i].first;
        if (currS >= targ) {
            ptr = i;
            break;
        }
    }
    deque<pair<ll, int>> dq;
    for (int i = 0; i <= ptr; i++) {
        dq.push_back(curr[i]);
    }
    priority_queue<pair<ll, int>> max2;
    for (int i = n-1; i > ptr; i--) {
        max2.push(curr[i]);
    }
    vector<pair<ll, int>> usesMax;
    while (true) {
        if (!dq.empty() && currS - dq.back().first >= targ) {
            currS -= dq.back().first;
            dq.pop_back();
            continue;
        }
        int sz = dq.size();
        if (sz <= goal) break;
        currS -= dq.front().first;
        pair<ll, int> rem = dq.front();
        dq.pop_front();
        if (currS >= targ) {
            max2.push(rem);
            continue;
        }
        dq.push_back(rem);
        currS += dq.front().first;
        if (!max2.empty() && max2.top().first > dq.back().first) {
            pair<ll, int> mx = max2.top();
            max2.pop();
            currS -= dq.back().first;
            max2.push(dq.back());
            dq.pop_back();
            currS += mx.first;
        }
    }
    vector<int> fin;
    vector<bool> ok(n, false);
    while (!dq.empty()) {
        fin.push_back(dq.front().second);
        dq.pop_front(); 
        ok[fin.back()] = true;
    }
    for (int i = 0; i < n; i++) {
        if (!ok[i]) fin.push_back(i);
    }
    return fin;
}
/*
int main() {
    int n; cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) cin >> p[i];
    vector<int> ret = solve(p);
    for (auto x: ret) cout << x << " ";
    cout << "\n";
}*/