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

#define ll long long

ll INF = 1e18;

int get_last(vector<pair<ll, int>> &arr, ll tot) {
    ll targ = (tot + 1) / 2;
    ll s = 0;
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        s += arr[i].first;
        if (s >= targ) return i;
    }
    assert(false);
    return -1;
}

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());
    for (int i = 0; i < n; i++) curr.push_back({0, 0});
    ll targ = (s + 1) / 2;
    int ptr = get_last(curr, s);
    ll currS = 0;
    deque<pair<ll, int>> dq;
    for (int i = 0; i <= ptr; i++) {
        currS += curr[i].first;
        dq.push_back(curr[i]);
    }
    vector<pair<ll, int>> max2;
    for (int i = ptr + 1; i < n; i++) {
        max2.push_back(curr[i]);
    }
    int currL = 0, currR = ptr;
    while (true) {
        if (!dq.empty() && currS - curr[currR].first >= targ) {
            currS -= curr[currR].first;
            currR--;
            continue;
        }
        int sz = currR - currL + 1;
        if (sz <= goal) break;
        
        pair<ll, int> rem = curr[currL];
        currL++;
        currS -= rem.first;
        
        if (currS >= targ) continue;

        if (!max2.empty()) {
            pair<ll, int> mx = max2.back();
            max2.pop_back();
            currS += mx.first;
            currR++;
            curr[currR] = mx;
        }
    }
    vector<int> fin;
    vector<bool> ok(n, false);
    for (int i = currL; i <= currR; i++) {
        fin.push_back(curr[i].second);
        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";
}*/