#include "partition.h"
#include <bits/stdc++.h>

using namespace std;
#define all(x) (x).begin(), (x).end()

using ll = long long;
#define int ll
#define pii pair<int, int>

vector<signed> solve(vector<signed> a) {
	int n = a.size();
	vector<signed> inds;
	for (int i = 0; i < n; i ++) {
		inds.push_back(i);
	}
	sort(all(inds), [&] (signed x, signed y) { return a[x] < a[y]; });
	int sum = 0, sumA = 0;
	set<pii> valsA, valsB; //pq if TLE
	for (int i = 0; i < (n + 1) / 2; i ++) {
		valsA.insert({a[inds[i]], inds[i]});
		sum += a[inds[i]];
		sumA += a[inds[i]];
	}
	for (int i = (n + 1) / 2; i < n; i ++) {
		sum += a[inds[i]];
		valsB.insert({a[inds[i]], inds[inds[i]]});
	}
	sum = (sum + 1) / 2;
	while (sumA < sum) {
		auto itA = valsA.begin();
		pii x = *itA;
		
		auto itB = valsB.end();
		itB --;
		pii y = *itB;
		
		sumA -= x.first;
		sumA += y.first;
		valsA.erase(x);
		valsB.erase(y);
		valsA.insert(y);
		valsB.insert(x);
	}
	vector<signed> ans;
	for (auto i : valsA) {
		// cout << "A: " << i.first << " " << i.second << '\n';
		ans.push_back(i.second);
	}
	for (auto i : valsB) {
		// cout << "B: " << i.first << " " << i.second << '\n';
		ans.push_back(i.second);
	}
	return ans;
}
