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

    sort(a.begin(), a.end());
    t = (t + 1) / 2;
    
    for(int i = 0; i < (n + 1) / 2; ++i) suff += a[n - 1 - i].f;
    
    int l, r;
    for(int off = 0;; off++) {
        if(off) suff += a[n / 2 - off].f;
        if(suff < t) continue;

        s = 0, l = 0, r = 0;
        while(r < n / 2 + off) 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;
}
