#include<vector>
#include<iostream>
#include<algorithm>
#include"partition.h"
using namespace std;
std::vector<int> solve(std::vector<int> A) {
	int n = A.size();
	vector<pair<int, int>>v;
	for (int i = 0; i < n; i++) {
		v.push_back({ A[i],i });
	}
	sort(v.begin(), v.end());
	vector<int>ans;
	for (int i = 0; i < n / 2 - 1; i++) {
		ans.push_back(v[i].second);
	}
	ans.push_back(v[n - 1].second);
	for (int i = n/2-1; i < n  - 1; i++) {
		ans.push_back(v[i].second);
	}




	return { ans };
}
