#include "partition.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long




std::vector<signed> solve(std::vector<signed> A) {
    int n = A.size();
    int k = n/2;
    int idx = 0;
    int s = 0; int s2 = 0;
    vector<pair<int,int>> tr(n);
    for (int i=0; i<n; i++) tr[i] = {A[i], i};
    sort(tr.begin(), tr.end());
    vector<int> a(n); for (int i=0; i<n; i++) a[i] = tr[i].first;
    for (int i=k; i<n; i++) s2+=a[i];
    for (int i=0; i<n; i++) s +=a[i];
    vector<signed> res;
    int f = 0;
    while (1){
        if (2*(s2 - a[n-1-idx]) < s){
            for (int i=0; i<idx; i++) res.push_back(i);
            for (int i=k; i<n-idx; i++) res.push_back(i);
            for (int i=idx; i<k; i++) res.push_back(i);
            for (int i=n-idx; i<n; i++) res.push_back(i);
            break;
        }
        if (idx >= k + (n%2)) {f=1; break;}
        s2 += a[idx] - a[n-1-idx]; idx++;
    }
    if ((n%2) && f){
        res.assign(n,0); iota(res.begin(), res.end(), 0);
    }
    for (int i=0; i<n; i++) res[i] = tr[res[i]].second;
    return res;
}
