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


#define ll long long 

std::vector<int> solve(std::vector<int> b) {
    
    vector <pair<int,int>> a;

    int n = b.size();
    for (int i = 0; i < n; i++) {
        a.emplace_back(b[i],i);
    }
    sort_heap(a.begin(),a.end());
    vector <ll> pref(n+1,0);
    for (int i = 0; i < n; i++) {
        ll last = (i==0)?0:pref[i-1];
        pref[i] = last + a[i].first;
    } 
    auto get = [&](int l, int r) {
        ll last = (l == 0)?0:pref[l-1];
        return pref[r] - last;
    };

    int s = n/2;

    int al = -1;
    int ar = -1;
    ll cur = LLONG_MAX;
    for (int l = n-s-1; l >= 0; l--) {
        int r = l + s - 1;
        ll sum = get(l,r);
        ll d = pref[n-1]/2-sum;
        if (d >= 0 && d < a.back().first) {
                cur = d;
                al = l;
                ar = r;
        }
    }

    vector <int> ans;
    if (al != -1) {
        for (int i = 0; i < al; i++) {
            ans.emplace_back(a[i].second);
        }
        for (int i = ar+1 ; i < n; i++) {
            ans.emplace_back(a[i].second);
        }
        for (int i = al; i <= ar; i++) {
            ans.emplace_back(a[i].second);
        }
        return ans;
    }
    
    ans.resize(n);
    iota(ans.begin(),ans.end(),0);
    return ans;
    
    
    
}
