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

vector<int> solve(vector<int> in) {
    int n = in.size(); ll T = 0, s = 0, suff = 0;
    vector<pair<ll, int>> a(n);
    vector<ll> rev(n);
    for(int i = 0; i < n; ++i) {
        a[i] = {in[i], i};
        T += in[i];
        rev[i] = in[i];
    }

    sort(a.begin(), a.end());
    sort(rev.rbegin(), rev.rend());

    ll t = (T + 1) / 2;

    int len = n / 2;
    for(int i = 0; i < len; ++i) suff += rev[i];
    for(; len < n && suff < t; ++len) suff += rev[len];
    
    int l = 0, r = 0;
    while(r < len) s += a[r++].f;
    while(s < t) s += a[r++].f - a[l++].f;

    vector<int> ans;
    for(int i = l; i < n; ++i) ans.push_back(a[i].s);
    for(int i = 0; i < l; ++i) ans.push_back(a[i].s);

    return ans;
}
