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

const int N=2e6+5;
int n;
ll all=0;
vector<pair<int, int>> v;
vector<int> ans;

void add(int l, int r, vector<pair<int, int>> &a) {
    for(int i=l; i<=r; i++)
        ans.push_back(a[i].second);
}
void clr() {
    ans.clear();
    v.clear();
    all=0;
}

std::vector<int> solve(std::vector<int> A) {
    clr();
    n=A.size();
    for(int i=0; i<n; i++)
        v.push_back({A[i], i});
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++)
        all+=A[i];
    ll l=0;
    ll mn=LLONG_MAX;
    int wh=0;
    bool f=0;
    for(int i=0; i<n; i++) {
        l+=v[i].first;
        ll r=all-l;
        if(max(l, r)>=(all+1)/2) {
            if(mn>abs(i+1-(n-1-i-1+1))) {
                mn=abs(i+1-(n-1-i-1+1));
                wh=i;
                if(r>l)
                    f=1;
                else
                    f=0;
            }
        }
    }
    ///cout << "diff: " << mn << endl;
    if(f) {
        add(wh+1, v.size()-1, v);
        add(0, wh, v);
    }
    else {
        add(0, wh, v);
        add(wh+1, v.size()-1, v);
    }
    return ans;
}