#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(), t = 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(), [](auto &a, auto &b) { return a < b; });
    t = (t + 1) / 2;
    
    int s, l, r;
    for(int off = 0;; off++) {
        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 < r; ++i) ans.push_back(a[i].s);
    for(int i = 0; i < l; ++i) ans.push_back(a[i].s);
    for(int i = r; i < n; ++i) ans.push_back(a[i].s);

    return ans;
}
