#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, suff = 0;
    vector<pair<int, int>> a(n);
    vector<int> rev = in;
    for(int i = 0; i < n; ++i) a[i] = {in[i], i}, T += in[i];

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

    ll t = (T + 1) / 2;

    for(int i = 0; i < n / 2; ++i) suff += rev[i];
    
    int l = 0, r = 0;
    for(int len = n / 2; len < n; suff += rev[len++]) {
        if(suff < t) continue;

        s = 0, l = 0, r = 0;
        while(r < len) s += a[r++].f;
        while(r < n && s < t) s += a[r++].f - a[l++].f;
        
        if(s >= t) break;
    }

    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;
}
