#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;
    iota(all(id),0ll);
    sort(all(id));
    // sort(all(id), [&](ll i, ll j){return ar[i]<ar[j];});
    ll m = (n+1)/2;
    swap(id[m-1], id[n-1]);
    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){
        while((sm-ar[id[m-1]])*2>=s){
            sm-=ar[id[m-2]];
            swap(id[m-2],id[m-1]);
            m--;
        }
        return id;
    }
    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;
}