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

int *A;
int cmp(const void *a, const void *b) {
    return A[*(const size_t *)a] - A[*(const size_t *)b];
}

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

    size_t p[A.size()];
    for (size_t i = 0; i < A.size(); i++) p[i] = i;
    qsort(p, A.size(), sizeof(size_t), cmp);

    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[A.size() - 1]];

    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[A.size() - ++suff]];
        }
    }

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

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