#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());
    
    deque<int> res, u;
    for(int i = 1;i<n;){
		if(op[i].first == op[i-1].first){
			u.push_front(op[i].second);
			u.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(n == 1)res.push_back(0);
	
	if(!res.empty()){
		for(int i = 0;i<(int)(res.size()-1)/2;i++){
		u.push_front(res[i]);
		}
		u.push_front(res.back());

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