#include "partition.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<iomanip>
#include<math.h>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

std::vector<int> solve(std::vector<int> A) {
	ll n = A.size();
	map<ll, vll> cnt;
	for (ll i = 0; i < n; i++) {
		cnt[A[i]].push_back(i);
	}
	vector<int> ans(n);
	ll p = 0;
	vpll rem;
	for (auto i : cnt) {
		ll mid = i.second.size() / 2;
		for (ll j = 0; j < mid; j++) {
			ans[p] = i.second[j], ans[n - p - 1] = i.second[i.second.size() - j - 1];
			p++;
		}
		if (i.second.size() % 2 == 1) {
			rem.push_back({ i.first, i.second[mid] });
		}
	}
	sort(rem.begin(), rem.end());
	ll s1 = 0, s2 = 0;
	ll s = p, e = n - p - 1;
	while (!rem.empty()) {
		if (s1 < s2) {
			s1 += rem.back().first;
			ans[s] = rem.back().second;
			s++;
		}
		else {
			s2 += rem.back().first;
			ans[e] = rem.back().second;
			e--;
		}
		rem.pop_back();
	}
	return ans;
}
