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

std::vector<int> solve(std::vector<int> A) {
	int n = A.size();
	vector<pair<int,int>> op;
	for(int i = 0;i<n;i++){
		op.push_back({A[i], i});
	}
	sort(op.begin(), op.end());
    
    vector<int>a, b, res, ans, ans2;
    for(int i = 1;i<n;){
		if(op[i].first == op[i-1].first){
			a.push_back(op[i].second);
			b.push_back(op[i-1].second);
			i += 2;
			if(i == n)res.push_back(op[n-1].second);
		}
		else{
			res.push_back(op[i-1].second);
			i += 1;
			if(i == n)res.push_back(op[n-1].second);
		}
	}
	
	if(!res.empty()){
		for(int i = 0;i<(int)(res.size()-1)/2;i++){
		a.push_back(res[i]);
		}
		a.push_back(res.back());

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