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

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    if (n == 1) return {0};
    int64_t sum = 0;
    std::vector<std::pair<int, int>> b(n);
    std::vector<int> idx(n);
    for (int i = 0; i < n; ++i) b[i] = {a[i], i};
    std::sort(b.begin(), b.end());
    for (int i = 0; i < n; ++i) a[i] = b[i].first, idx[i] = b[i].second;
    if (n == 2) return {idx[1], idx[0]};
    for (auto u: a) sum += u;
    int64_t sm = 0, nd = (sum + 1) / 2;
    int l = 0;
    int res = n + 5, optl = -1, optr = -2;
    optl = 0, optr = (n + 1) / 2 - 2;
    for (int i = optl; i <= optr; ++i) sm += a[l];
    while (sm < nd - a.back()) {
        sm -= a[optl++];
        sm += a[++optr];
    }
    std::vector<int> res2;
    assert(sm < nd);
    for (int i = optl; i <= optr; ++i) res2.emplace_back(idx[i]);
    res2.emplace_back(idx[n - 1]);
    for (int i = 0; i < optl; ++i) res2.emplace_back(idx[i]);
    for (int i = optr + 1; i + 1 < n; ++i) res2.emplace_back(idx[i]);
    return res2;
}
