#include "partition.h"
#include <iostream>
using namespace std;
#include <map>
#include <queue>
#include <cassert>

const int N = 2e6 + 10;

pair<int, int> v[N];

std::vector<int> solve(std::vector<int> A) {
	int n = A.size();
	int sum = 0;
	priority_queue<pair<int,int>> pq;
	for (int i = 0; i < n; i++) {
		v[i] = { A[i], i };
		sum += A[i];
		pq.push({ -A[i], i });
	}
	sum = (sum + 1) / 2;
	int s = 0;
	vector<int> res;
	for (int i = 0; i < n; i++) {
		v[i] = pq.top();
		pq.pop();
		res.push_back(v[i].second);
		v[i].first = -v[i].first;
	}
	for (int i = 0; i < (n + 1) / 2; i++) {
		s += v[i].first;
	}
	int l = (n + 1) / 2 - 1, r = n - 1;
	while (l >= 0 && s < sum) {
		s -= v[l].first;
		s += v[r].first;
		swap(res[l], res[r]);
		l--, r--;
	}
	return res;
}
