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

long long pref[100005];

vector<int> solve(vector<int> A){
    int n = A.size();
    vector<pair<int, int>> alt(n);
    for(int i=0;i<n;++i){alt[i].first=A[i]; alt[i].second=i;}

    sort(alt.begin(), alt.end());

    pref[0]=0;
    for(int i=0;i<n;++i) pref[i+1] = pref[i]+alt[i].first;

    long long t = (pref[n]/2) + (pref[n]%2);
    int amount = (n/2) + (n%2);
    
    if(pref[amount]>=t){
        vector<int> res;
        for(auto i : alt) res.push_back(i.second);
        return res;
    }
    else{
        long long sum = pref[amount];
        
        int i = amount-1;
        int j = n-1;
        while(sum < t){
            if(j<=amount) break;

            swap(alt[j], alt[i]); sum += alt[i].first-alt[j].first;
            i--;
            j--;
        }

        vector<int> res;
        for(auto i : alt) res.push_back(i.second);
        return res;
    }
}