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

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

using ll = long long;
const int N = 4e6 + 5;

int valsA[N], valsB[N];

vector<signed> solve(vector<signed> a) {
	int n = a.size();
	ll sum = 0, sumA = 0;
	int fa = 0, la = 0, fb = 0, lb = 0;
	vector<signed> tot;
	for (int i = 0; i < n; i ++) {
		tot.push_back(i);
	}
	for (int i = 0; i < (n + 1) / 2; i ++) {
		valsA[la ++] = i;
		sum += a[i];
		sumA += a[i];
	}
	for (int i = (n + 1) / 2; i < n; i ++) {
		sum += a[i];
		valsB[lb ++] = i;
	}
	sum = (sum + 1) / 2;
	if (sumA >= sum) {
		sumA = 0;
		fa = 0, la = 0, fb = 0, lb = 0;
		for (int i = 0; i < (n + 1) / 2; i ++) {
			valsA[la ++] = n - i - 1;
			sumA += a[n - i - 1];
		}
		for (int i = (n + 1) / 2; i < n; i ++) {
			valsB[lb ++] = n - i - 1;
		}
		if (sumA >= sum) {
			ll sum1 = 0;
			for (int i = 0; i < (n - 1) / 2; i ++) {
				sum1 += a[i];
			}
			if (sum1 < sum) {
				return tot;
			}
			tot.clear();
			for (int i = n - 1; i >= 0; i --) {
				tot.push_back(i);
			}
			return tot;
		}
	}
	while (sumA < sum) {
		auto x = valsA[fa ++];
		auto y = valsB[fb ++];
		
		sumA -= a[x]
		sumA += a[y];
		
		valsA[la ++] = y;
		valsB[lb ++] = x;
	}
	vector<signed> ans;
	for (int i = fa; i < la; i ++) {
		ans.push_back(valsA[i]);
	}
	for (int i = fb; i < lb; i ++) {
		ans.push_back(valsB[i]);
	}
	return ans;
}
