#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> A) {
    int n = A.size();
    unordered_map<int,vector<int>>mp;
    for(int i = 0;i<n;i++){
		mp[A[i]].push_back(i);
	}
	
	vector<int>res, ans, ans2;
	long long sum = 0;
	for(auto to : mp){
		if(to.second.size() % 2 == 1){
			res.push_back(to.second.back());
			sum += to.first;
		}
		for(int i = 1;i<to.second.size();i+=2){
			ans.push_back(to.second[i-1]);
			ans2.push_back(to.second[i]);
		}
	}
	
	if(!res.empty()){
		for(int i = 0;i<(int)(res.size()-1)/2;i++){
		ans.push_back(res[i]);
		}
		ans.push_back(res.back());

		for(int i = (res.size()-1)/2;i<(int)res.size()-1;i++){
			ans2.push_back(res[i]);
		}
	}
	
	vector<int>u;
	for(auto to : ans)u.push_back(to);
	for(auto to : ans2)u.push_back(to);
	
	return u;
	
	
}
