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

using ll = long long;

int n;

std::vector<int> solve(std::vector<int> A) {
    n = A.size();

    std::vector<int> ind(n);
    for (int i = 0; i < n; i++)
        ind[i] = i;

    ll sum_total = 0;
    for (const int & x : A)
        sum_total += x;

    std::sort(ind.begin(), ind.end(), [&](const int & x, const int & y) {return A[x] < A[y];});

    ll sum_first_half = 0;

    for (int i = 0; i < (n + 1) / 2; i++) {
        sum_first_half += A[ind[i]];
    }

    int idx = 0;

    while (sum_first_half + sum_first_half < sum_total) {
        sum_first_half += A[ind[n - 1 - idx]] - A[ind[idx]];
        std::swap(ind[idx], ind[n - 1 - idx]);
        idx++;
    }

    std::sort(ind.begin(), ind.begin() + (n + 1) / 2, [&](const int & x, const int & y) {return A[x] < A[y];});

    return ind;
}
