#include "partition.h"
#include <bits/stdc++.h>

#define int long long

using namespace std;

using pii = pair<int, int>;

vector<int> solve(vector<int> A) {
    int n = A.size();
    vector<pii> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = {A[i], i};
    }
    sort(a.begin(), a.end());
    int S = accumulate(A.begin(), A.end(), 0ll);
    int s = 0, pl = (n + 1) / 2;
    for (int i = 0; i < pl; i++) {
        s += a[i].first;
    }
    for (int i = (n - 1) / 2; i >= 0; i--) {
        s -= a[i].first;
        s += a[i + n / 2].first;
        pl--;
        if (s * 2 >= S) {
            break;
        }
    }
    vector<int> ans;
    ans.reserve(n);
    for (int i = 0; i < pl; i++) {
        ans.push_back(a[i].second);
    }
    for (int i = pl + n / 2; i < n; i++) {
        ans.push_back(a[i].second);
    }
    for (int i = pl; i < pl + n / 2; i++) {
        ans.push_back(a[i].second);
    }
    return ans;
}
