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