#include "partition.h"
#include <algorithm>
#include <cstdint>
#include <random>
using namespace std;

vector<int> solve(vector<int> A) {
	int64_t s = 0, s2 = 0;
	for (const int &i : A) s += i;
	vector<pair<int, int>> a(A.size());
#pragma GCC ivdep
	for (int i = 0; i < A.size(); i++) a[i] = {A[i], i};
	if (!ranges::is_sorted(a, [](auto &x, auto &y) { return x.first < y.first; })) {
		ranges::shuffle(a, std::mt19937(std::random_device()()));
		ranges::sort(a.begin(), min(a.end(), a.begin() + 101));
		const int x = a[min<int>(50, a.size() / 2)].first;
		const auto it = ranges::partition(a, [&x](auto &y) { return y.first < x; }).end(); // haha funny pun
		ranges::sort(a.begin(), it, [](auto &x, auto &y) { return x.first < y.first; });
		ranges::sort(it, a.end(), [](auto &x, auto &y) { return x.first < y.first; });
	}
	const int n = a.size() + 1 >> 1;
	for (int i = 0; i < n; i++) s2 += a[i].first;
	for (int i = n - 1; i >= 0 && s2 << 1 < s; i--) {
		s2 -= a[i].first;
		swap(a[i], a[i + a.size() - n]);
		s2 += a[i].first;
	}
	vector<int> res(a.size());
#pragma GCC ivdep
	for (int i = 0; i < a.size(); i++) res[i] = a[i].second;
	return res;
}