#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;
        }
    }
    int currL = 0, currR = ptr;
    vector<pair<int, int>> max2;
    for (int i = n-1; i > ptr; i--) {
        max2.push_back(curr[i]);
    }
    reverse(max2.begin(), max2.end());
    vector<pair<int, int>> usesMax;
    while (true) {
        int sz = currR - currL + 1 + usesMax.size();
        if (sz <= goal) break;
        currS -= curr[currL].first;
        currL++;
        if (currS >= targ) continue;
        if (!max2.empty()) {
            usesMax.push_back(max2.back());
            currS += usesMax.back().first;
            max2.pop_back();
        }
    }
    vector<int> fin;
    vector<bool> ok(n, false);
    for (int i = currL; i <= currR; i++) {
        fin.push_back(curr[i].second);
        ok[curr[i].second] = true;
    }
    for (auto [v, id]: max2) {
        ok[id] = true;
        fin.push_back(id);
    }
    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";
}*/