#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();
	vpll arr(n);
	for (ll i = 0; i < n; i++) {
		arr[i] = { A[i], i };
	}
	sort(arr.begin(), arr.end());
	vector<int> ans(n);
	ll p = 0;
	vpll rem;
	ll sum = 0;
	
	vll now = { arr[0].second };
	for (ll i = 1; i < n; i++) {
		if (arr[i].first == arr[i - 1].first) {
			now.push_back(arr[i].second);
		}
		else {
			ll mid = now.size() / 2;
			for (ll j = 0; j < mid; j++) {
				ans[p] = now[j], ans[n - p - 1] = now[now.size() - j - 1];
				p++;
			}
			if (now.size() % 2 == 1) {
				rem.push_back({arr[i-1].first, now[mid]});
				sum += arr[i-1].first;
			}
			now.clear();
			now = { arr[i].second };
		}
	}
	ll mid = now.size() / 2;
	for (ll j = 0; j < mid; j++) {
		ans[p] = now[j], ans[n - p - 1] = now[now.size() - j - 1];
		p++;
	}
	if (now.size() % 2 == 1) {
		rem.push_back({ arr[n - 1].first, now[mid] });
		sum += arr[n - 1].first;
	}
	if (rem.size() <= 2) {
		reverse(rem.begin(), rem.end());
		for (auto i : rem) {
			ans[p] = i.second;
			p++;
		}
		return ans;
	}
	ll want = (rem.size() + 1) / 2;
	want--;
	ll s_need = (sum + 1) / 2;
	ll m = rem.size();
	vll pref(m);
	pref[0] = rem[0].first;
	for (ll i = 1; i < m; i++) {
		pref[i] = pref[i - 1] + rem[i].first;
	}
	for (ll j = want - 1; j < m - 1; j++) {
		ll got = pref[j] - (j -want < 0 ? 0 : pref[j - want]);
		if (got + rem.back().first >= s_need) {
			for (ll i = j - want + 1; i <= j; i++) {
				ans[p] = rem[i].second;
				p++;
			}
			ans[p] = rem.back().second;
			p++;
			for (ll i = 0; i < j - want + 1; i++) {
				ans[p] = rem[i].second;
				p++;
			}
			for (ll i = j + 1; i < m - 1; i++) {
				ans[p] = rem[i].second;
				p++;
			}
			break;
		}
	}
	return ans;
}
