#include "partition.h"
#include <algorithm>
#include <cstdint>
#include <unordered_map>
#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;
	unordered_map<int, vector<int>> m;
	for (int i = 0; i < A.size(); i++) m[A[i]].push_back(i);
	a.reserve(A.size());
	vector<pair<int, vector<int>>> vm(m.begin(), m.end());
	ranges::sort(vm, [](auto &x, auto &y) { return x.first < y.first; });
	for (auto &[x, y] : vm) for (const int i : y) a.emplace_back(x, i);
	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;
}