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




std::vector<signed> solve(std::vector<signed> A) {
    int n = A.size();
    int k = n/2;
    int idx = 0;
    ll s = 0; ll s2 = 0;
    //vector<pair<int,int>> tr(n);
    //for (int i=0; i<n; i++) tr[i] = {A[i], i};
    //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(n,0); int nx = 0; 
    int f = 0;
    while (1){
        if (2*(s2 - A[n-1-idx]) < s){
            for (int i=0; i<idx; i++) res[nx++] = i;
            for (int i=k; i<n-idx; i++) res[nx++] = i;
            for (int i=idx; i<k; i++) res[nx++] = i;
            for (int i=n-idx; i<n; i++) res[nx++] = i;
            break;
        }
        if (idx >= k + (n%2)) {f=1; break;}
        s2 += A[idx] - A[n-1-idx]; idx++;
    }
    if ((n%2) && f){
        for (int i=0; i<n; i++) res[i] = i;
    }
    //for (int i=0; i<n; i++) res[i] = tr[res[i]].second;
    return res;
}
