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

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

using ll = long long;
#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);
	}
	//if (n <= 1e6)
		//sort(all(inds), [&] (signed x, signed y) { return a[x] < a[y]; });
	ll sum = 0, sumA = 0;
	queue<pii> valsA, valsB;
	for (int i = 0; i < (n + 1) / 2; i ++) {
		valsA.push({a[inds[i]], inds[i]});
		sum += a[inds[i]];
		sumA += a[inds[i]];
	}
	for (int i = n - 1; i >= (n + 1) / 2; i --) {
		sum += a[inds[i]];
		valsB.push({a[inds[i]], inds[i]});
	}
	sum = (sum + 1) / 2;
	while (sumA < sum) {
		auto x = valsA.front();
		auto y = valsB.front();
		
		sumA -= x.first;
		sumA += y.first;
		
		valsA.pop();
		valsB.pop();
		valsA.push(y);
		valsB.push(x);
	}
	vector<signed> ans;
	while (!valsA.empty()) {
		ans.push_back(valsA.front().second);
		valsA.pop();
	}
	while (!valsB.empty()) {
		ans.push_back(valsB.front().second);
		valsB.pop();
	}
	return ans;
}
