#include "partition.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void coutv(vector<int> v) {
    for (auto u : v) {
        cout << u << endl;
    }
}
// < (n + 1) / 2
vector<int> solve(vector<int> A) {
    ll n = A.size();
    vector<int> ans(n);
    ll S = 0;
    for (auto x : A)
    {
        S += (ll) x;
    }
    vector<pair<ll, ll>> soo;
    for (ll i = 0; i < n; i++)
    {
        soo.push_back({A[i], i});
    }
    sort(soo.begin(), soo.end());
    ll csm = 0;
    for (ll i = 0; i < (n + 1) / 2; i++)
    {
        csm += soo[i].first;
    }
    ll iter = 0;
    while ((2 * csm) < S)
    {
        csm += soo[n - iter - 1].first;
        csm -= soo[iter].first;
        swap(soo[iter], soo[n - iter - 1]);
        iter++;
    }
    vector<pair<ll, ll>> soot;
    for (ll i = 0; i < (n + 1) / 2; i++)
    {
        soot.push_back(soo[i]);
    }
    sort(soot.begin(), soot.end());
    for (ll i = 0; i < (n + 1) / 2; i++)
    {
        soo[i] = soot[i];
    }
    for (ll i = 0; i < n; i++)
    {
        ans[i] = soo[i].second;
    }
    //coutv(ans);
    return ans;
}

/*int main()
{
    ll n;
    cin >> n;
    vector<int> A(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    solve(A);
}*/
