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

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 = 0, sl = 0;
    for (int i = 0; i < n; i++) {
        s += a[i].first;
        pl++;
        if (s * 2 >= S) {
            break;
        }
    }
    while (pl + sl > n / 2) {
        pl--;
        s -= a[pl].first;
        if (s * 2 < S) {
            sl++;
            s += a[n - sl].first;
        }
    }
    vector<int> ans;
    ans.reserve(n);
    for (int i = 0; i < pl; i++) {
        ans.push_back(a[i].second);
    }
    for (int i = sl - 1; i >= 0; i--) {
        ans.push_back(a[n - 1 - i].second);
    }
    for (int i = pl; i < n - sl; i++) {
        ans.push_back(a[i].second);
    }
    return ans;
}
