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

std::vector<int> solve(std::vector<int> a) {
    int n = a.size();
    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;
    for (auto u: a) sum += u;
    int64_t sm = 0;
    int l = 0;
    int res = n + 5, optl = -1, optr = -2;
    int64_t nd = (sum + 1) / 2;
    for (int r = 0; r < n; ++r) {
        sm += a[r];
        if (sm < nd) continue;
        if (res > std::abs(r - l + 1 - (n - (r - l + 1)))) {
            res = std::abs(r - l + 1 - (n - (r - l + 1)));
            optl = l;
            optr = r;
        }
        while (sm >= nd) sm -= a[l++];
    }
    std::vector<int> res2;
    for (int i = optl; i <= optr; ++i) res2.emplace_back(idx[i]);
    for (int i = 0; i < optl; ++i) res2.emplace_back(idx[i]);
    for (int i = optr; i < n; ++i) res2.emplace_back(idx[i]);
    return res2;
}
