#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);
    perm.erase(std::find(perm.begin(), perm.end(), mx));
    std::sort(perm.begin(), perm.end(), [&](int x, int y) {
        return a[x] > a[y];
    });
    int L, R;
    {
        R = 0;
        ll s = 0;
        while (R < perm.size() && s + a[perm[perm.size() - R - 1]] <= (S - 1) / 2) {
            s += a[perm[perm.size() - R++ - 1]];
        }
    }
    {
        ll s = 0;
        L = 0;
        while (L < perm.size() && s < (S + 1) / 2 - a[mx]) s += a[perm[L++]];
        L--;
    }
    auto check = [&](int cnt) -> std::vector<bool> {
        std::vector<bool> used(n);
        int ptr = cnt;
        ll s = 0;
        for (int i = 1; i <= cnt; ++i) s += a[perm[perm.size() - i]];
        if (s > (S - 1) / 2) return {};
        for (auto i : perm) {
            if (ptr > 0 && s - a[perm[perm.size() - ptr]] + a[i] <= (S - 1) / 2) {
                s = s - a[perm[perm.size() - ptr]] + a[i];
                --ptr;
                used[i] = true;
            }
        }
        for (int i = 1; i <= ptr; ++i) used[perm[perm.size() - i]] = true;
        if (s >= (S + 1) / 2 - a[mx]) return used;
        return {};
    };
    for (int i = (n - 1) / 2; i >= 0; --i) {
        if (L <= i && i <= R) {
            auto used = check(i);
            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;
        }
    }
    assert(false);
}