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

using namespace std;

vector<int> solve(vector<int> v) {
    int n = v.size();
    vector <int> ans;
    vector <pair <int, int>> sorted;

    long long sumtotal = 0;
    for (int i = 0; i < n; i++) {
        sorted.push_back({v[i], i});
        sumtotal += 1LL * v[i];
    }

    long long half = (sumtotal + 1) / 2;

    sort(sorted.begin(), sorted.end());

    long long sum = 0;
    for (int i = 0; i <= n / 2; i++) {
        sum += 1LL * sorted[i].first;
    }

    int point1 = n / 2, point2 = n - 1;
    while (sum < half) {
        sum += 1LL * sorted[point2].first;
        sum -= 1LL * sorted[point1].first;

        swap(sorted[point1], sorted[point2]);
        point1--;
        point2--;
    }

    for (int i = 0; i < n; i++) {
        ans.push_back(sorted[i].second);
    }

    return ans;
}


