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


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(a.begin(),a.end());
    vector <int> pref(n+1,0);
    for (int i = 0; i < n; i++) {
        int last = (i==0)?0:pref[i-1];
        pref[i] = last + a[i].first;
    } 
    auto get = [&](int l, int r) {
        int last = (l == 0)?0:pref[l-1];
        return pref[r] - last;
    };

    int s = n/2;

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

    // if (al == -1) return {};
    
    // cout << al << " " << ar << endl;
 vector <int> ans;
    if (al == -1) {
        ans.assign(n,0);
        iota(ans.begin(),ans.end(),0);
    } else {
       
        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;
    
    
}
