#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>
const int N = 2e6 + 5;

pair<int, int> valsA[N], valsB[N];

vector<signed> solve(vector<signed> a) {
	int n = a.size();
	vector<signed> inds;
	for (int i = 0; i < n; i ++) {
		inds.push_back(i);
	}
	nth_element(inds.begin(), inds.begin() + (n + 1) / 2, inds.end(), [&] (signed x, signed y) { return a[x] < a[y]; });
	ll sum = 0, sumA = 0;
	int fa = 0, la = 0, fb = 0, lb = 0;
	for (int i = 0; i < (n + 1) / 2; i ++) {
		valsA[la ++] = {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[lb ++] = {a[inds[i]], inds[i]};
	}
	sum = (sum + 1) / 2;
	while (sumA < sum) {
		auto x = valsA[fa ++];
		auto y = valsB[fb ++];
		
		sumA -= x.first;
		sumA += y.first;
		
		valsA[la ++] = y;
		valsB[lb ++] = x;
	}
	vector<signed> ans;
	for (int i = fa; i < la; i ++) {
		ans.push_back(valsA[i].second);
	}
	for (int i = fb; i < lb; i ++) {
		ans.push_back(valsB[i].second);
	}
	return ans;
}
