#include "partition.h"
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>

std::vector<int> solve(std::vector<int> A) {
    long long sum = 0;
    for (const auto x : A) sum += x;

    std::vector<size_t> p(A.size());
    for (size_t i = 0; i < A.size(); i++) p[i] = i;
    std::stable_sort(p.begin(), p.end(), [&A] (const auto a, const auto b) { return A[a] < A[b]; });

    int l = 0, r = 0, suff = 1;
    long long s = 0;
    for (const auto i : p) {
        if (s + A[i] >= sum / 2 + sum % 2) break;
        r++;
        s += A[i];
    }
    s += A[p.back()];

    const auto goal = A.size() / 2 + A.size() % 2;
    while (l < r && r - l + suff > goal) {
        s -= A[p[l++]];
        if (s < sum / 2 + sum % 2) {
            if (r + suff >= A.size()) {
                l--;
                break;
            }
            s += A[p[p.size() - ++suff]];
        }
    }

    std::vector<int> ans;
    ans.reserve(p.size());
    for (int i = l; i < r; i++) ans.push_back(p[i]);
    for (int i = p.size() - suff; i < p.size(); i++) ans.push_back(p[i]);
    for (int i = 0; i < l; i++) ans.push_back(p[i]);
    for (int i = r; i < p.size() - suff; i++) ans.push_back(p[i]);
    return ans;
}

/*
2 2 2 2 2 3 3 3
2 2 3 3
*/
