#include <iostream>

#include<vector>

#include<map>

#include<algorithm>

#include "partition.h"

using namespace std;

vector<int> solve(vector<int> A) {
	vector<int> sol;
	map<int, int> fr;
	bool par = true;
	bool pow2 = true;
	bool cons = true;
	for (int i = 0; i < A.size(); ++i) {
		fr[A[i]]++;
		if (A[i] != (1 << i)) pow2 = false;
		if (A[i] != i + 1) cons = false;
	}
	for (auto x : A) {
		if (fr[x] % 2 == 1) par = false;
	}
	if (par == true) {
		int s = 0;
		int f = 0;
		map<int, int> aux;
		vector<int> h1;
		vector<int> h2;
		for (int i = 0; i < A.size(); ++i) {
			aux[A[i]]++;
			if (aux[A[i]] <= fr[A[i]] / 2) {
				h1.push_back(i);
			}
			else {
				h2.push_back(i);
			}
		}
		for (auto p : h1) sol.push_back(p);
		for (auto p : h2) sol.push_back(p);
		return sol;
	}
	if (pow2 == true) {
		reverse(A.begin(), A.end());
		return A;
	}

}


