#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(), greater<pair<int, int>>());
    for(int i=0; i<n; i++)
        all+=A[i];
    ll l=0;
    int wh=0, mn=2*n;
    ll ansl=0, ansr=0;
    for(int i=0; i<n; i++) {
        l+=v[i].first;
        if(l>all/2) {
            ll r=all-l;
            int curr=abs(2*i+2-n);
            if(mn>curr) {
                mn=curr;
                wh=i;
                ansl=l, ansr=r;
            }
        }
    }
    ///cout << "diff: " << mn << " " << ansl << " " << ansr << endl;
    add(0, wh, v);
    add(wh+1, v.size()-1, v);
    return ans;
}
