#include "partition.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    vector<pair<int, int>> pos(n);
    for (int i = 0; i < n; ++i) {
        pos[i] = { a[i],i };
    }
    vector<int> answ;
    sort(pos.begin(), pos.end());
    if (n == 1) {
        return { 0 };
    }
    if (n == 2) {
        return { 0,1 };
    }
    vector<bool> vis(n+1,0);
    int x = (n + 1) / 2;
    vector<ll> prefx(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        ll o = a[pos[i-1].second];
        prefx[i] = prefx[i - 1] + o;
    }
    ll s = prefx[n];
    ll cur = 0ll;
    for (int i = n-1; i >= 0; --i) {
        if (x == 1) {
            break;
        }
        ll o = a[pos[i].second];
        if (o + prefx[x - 2] + cur < s / 2) {
            cur += o;
            answ.push_back(pos[i].second);
            vis[i] = 1;
            x--;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        if (!vis[i]) {
           answ.push_back(pos[i].second);
        }
    }
    return answ;
}