#include "partition.h"
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std;

vector<int> freq(1000005);
std::vector<int> solve(std::vector<int> A) {
	vector<pair<int, int>> a_sorted;
	a_sorted.reserve(A.size());
	long long total_sum = 0;
	for (int i = 0; i < A.size(); i++) {
		int x = A[i];
		total_sum += x;
		a_sorted.emplace_back(x, i);
	}
	sort(a_sorted.begin(), a_sorted.end());
	vector<int> first_half;
	vector<int> second_half;
	first_half.reserve(A.size());
	second_half.reserve(A.size());
	long long current_sum = 0;
	for (int i = a_sorted.size() - 1; i >= 0; i--) {
		if (1ll * a_sorted[i].first + current_sum <= total_sum / 2) {
			first_half.push_back(a_sorted[i].second);
		} else {
			second_half.push_back(a_sorted[i].second);
		}
	}
	vector<int> ans;
	ans.reserve(A.size());
	for (auto i : second_half) {
		ans.push_back(i);
	}
	for (auto i : first_half) {
		ans.push_back(i);
	}
	return ans;
}
