#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> solve(vector<int> A) {
	if ((int)A.size()==0) return {};
	if ((int)A.size()==1) return {0};
	vector <pair<int,int>> B; int n=(int)A.size();
	for (int i=0; i<n; i++) B.push_back({A[i],i});
	sort(B.begin(),B.end()); vector <int> va;
	if (n%2==0){
		for (int i=1; i<=n/2; i++) va.push_back(n-i),va.push_back(i-1);
		if (n==2) return {1,0};
		if ((n/2)%2==0) swap(va[n/2-1],va[n/2+1]); 
		return va;
	}
	else{
		if ((n-1)%4==0){
			for (int i=0; i<(n-1)/4; i++) va.push_back(i),va.push_back(n-i-1);
			va.push_back(n/2);
			for (int i=(n-1)/4; i<n/2; i++) va.push_back(i),va.push_back(n-i-1);
		}
		else{
			int x=(n-1)/2;
			for (int i=0; i<(x-1)/2; i++) va.push_back(i),va.push_back(n-i-1);
			va.push_back(n/2-1); va.push_back(n/2); va.push_back(n/2+1); 
			for (int i=(x-1)/2; i<x-1; i++) va.push_back(i),va.push_back(n-i-1);
		} return va;
	}
}
