#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#include "partition.h"
using namespace std;
using ll = int;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
std::vector<int> solve(std::vector<int> ar) {
    ll n = ar.size();
    vector<int> id(n);
    ll mx = 0;
    for(ll i = 0; i < n; ++i)if(ar[i]>ar[mx])mx=i;
    ll m = (n-1)/2;
    for(ll i=0,j = 0; i < n; ++i){
        if(j==mx)j++;
        if(i==m){
            id[i]=mx;
        }
        else{
            id[i]=j++;
        }
    }
    long long s=0, sm=0;
    for(ll i = 0 ;i < n; ++i){
        if(i<m)sm+=ar[id[i]];
        s+=ar[id[i]];
    }
    if(sm*2>=s){
        swap(id[m],id[m+1]);
        m = n-1-(m+1);
        reverse(all(id));
        s=0, sm=0;
        for(ll i = 0 ;i < n; ++i){
            if(i<m)sm+=ar[id[i]];
            s+=ar[id[i]];
        }
    }
    for(ll i = 0; i < m-1 && sm*2<s; ++i){
        swap(id[i],id[m+i]);
        sm += ar[id[i]]-ar[id[i+m]];
    }
    return id;
}