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

using ll = long long;

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    ll S = std::accumulate(a.begin(), a.end(), 0ll);
    int mx = std::max_element(a.begin(), a.end()) - a.begin();
    std::vector<int> perm(n);
    std::iota(perm.begin(), perm.end(), 0);
    std::sort(perm.begin(), perm.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    std::vector<bool> used(n);
    ll s = 0;
    int cnt = 0;
    for (auto i : perm) {
        if (i == mx || s + a[i] > (S - 1) / 2 || cnt >= (n - 1) / 2) continue;
        used[i] = true;
        s += a[i];
        ++cnt;
    }
    std::vector<int> ret;
    for (int i = 0; i < n; ++i) {
        if (used[i]) ret.push_back(i);
    }
    ret.push_back(mx);
    for (int i = 0; i < n; ++i) {
        if (i == mx) continue;
        if (!used[i]) ret.push_back(i);
    }
    return ret;
}