#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;
    int sum=0;
    for (int i=1; i<=n; i++) {
    	sum+=arr[i].f;
	}
    sort(arr+1,arr+1+n);
	int ind=(n+1)/2;
	swap(arr[n],arr[ind]);
	int sum2=0;
	for (int i=1; i<=ind-1; i++) {
		sum2+=arr[i].f;
	}
	int val=(sum+1)/2-arr[ind].f;
	for (int i=1; i<=ind-1; i++) {
		if (sum2>=val) break;
		int ind2=n-i+1;
		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;
}