#include "partition.h"
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <random>
#include <chrono>
#include <set>
#include <unordered_map>
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using namespace std;

#define V vector
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)
#define pb push_back
#define ll long long 
#define all(v) v.begin(), v.end()
#define sz(x) int(x.size())
#define pli pair<ll, int>
#define ff first
#define ss second

vector<int> solve(std::vector<int> a) {
	V<pli> tv;
	int n = sz(a);
	ll s = 0;
	rep(i, 0, n - 1, 1) {
		tv.pb({ a[i], i });
		s += a[i];
	}
	s = (s + 1) >> 1;
	sort(all(tv));
	//rep(i, 0, n - 1, 1) {
	//	cout << tv[i].ff << " " << tv[i].second << endl;
	//}
	//return{};
	V<int> ans(n);


	V<ll> pref(n, 0);
	pref[0] = tv[0].ff;
	rep(i, 1, n - 1, 1) {
		pref[i] = pref[i - 1] + tv[i].ff;
	}

	auto psum = [&](int x) {
		if (x == 0)
			return 0ll;
		return pref[x - 1];
	};
	auto ssum = [&](int x) {
		if (x == n)
			return pref[n - 1];
		return pref[n - 1] - pref[n - x - 1];
	};
	//rep(i, 1, n, 1) {
	//	cout << ssum(i) << " ";
	//}
	//cout << endl;
	//return {};
	int goal = (n + 1) >> 1;
	int good = -1;
	rep(i, 0, goal, 1) {
		if (s <= psum(i) + ssum(goal - i))
			good = i;
	}
	//cout << good << endl;
	//return {};
	rep(i, 0, good - 1, 1) {
		ans[i] = tv[i].ss;
	}
	int it = good;
	repl(i, n - 1, n - goal + good, 1) {
		ans[it] = tv[i].ss;
		++it;
	}

	V<bool> vis(n, false);
	rep(i, 0, it - 1, 1)
		vis[ans[i]] = true;
	rep(i, 0, n - 1, 1) {
		if (!vis[i])
			ans[it++] = i;
	}
	return ans;
}
