#include "partition.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
int n;
vector<int> solve(vector<int> A) {
    n=A.size();
	vector<int> vv;
	for (int i=1; i<=n; i++) vv.pb(i-1);
    long long sum=0;
    pii mx={0,0};
    for (int i=1; i<=n; i++) {
    	sum+=A[i-1];
    	mx=max(mx,{A[i-1],i});
	}
	int ind=(n+1)/2;
	swap(A[mx.s-1],A[ind-1]);
	swap(vv[mx.s-1],vv[ind-1]);
	long long sum2=0;
	for (int i=1; i<=ind-1; i++) {
		sum2+=A[i-1];
	}
	long long val=(sum+1)/2-A[ind-1];
	if (sum2<val) {
		for (int i=1; i<=ind-1; i++) {
			if (sum2>=val) break;
			int ind2=n-i+1;
			if (A[i-1]<A[ind2-1]) {
				sum2-=A[i-1]-A[ind2-1];
				swap(vv[i-1],vv[ind2-1]);
			}
		}
	}
	else if (sum2*2>=sum) {
		for (int i=1; i<=ind-1; i++) {
			if (sum2*2<sum) break;
			int ind2=n-i+1;
			if (A[i-1]>A[ind2-1]) {
				sum2-=A[i-1]-A[ind2-1];
				swap(vv[i-1],vv[ind2-1]);
			}
		}
	}
	return vv;
}