// #pragma GCC optimize("O3,unroll-loops")
#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

vector<int> solve(vector<int> A) {
    int N = A.size();
    // sort(A.begin(), A.end());
    ll S = 0;
    // int bst = INT_MAX;
    // int r = -1;
    // ll pre = 0, suf = 0;
    // for(int i = 1; i <= N; i++){
    //     pre += A[i - 1].first, suf += A[N - i].first;
    //     if(pre < (S + 1) / 2 && suf >= (S + 1) / 2){
    //         int c = abs(i - (N - i));
    //         if(c < bst)
    //             bst = c, r = i;
    //     }
    // }
    ll suml = 0, sumr = 0;
    int Ll = 0, Lr = N / 2 - 1, Rl = N / 2, Rr = N - 1;
    for (int i = 0; i < N; i++) {
        S += A[i];
        if (i < N / 2)
            suml += A[i];
        else
            sumr += A[i];
    }
    bool swapped = false;
    if (suml > sumr)
        swap(Ll, Rl), swap(Lr, Rr), swap(suml, sumr), swapped = true;
    vector<int> rest, o;
    if (Lr - Ll > Rr - Rl) {
        int i = swapped ? Ll++ : Lr--;
        suml -= A[i];
        swapped ? Rr++ : Rl--;
    }
    rest.reserve(N), o.reserve(N);
    while (Lr >= Ll && suml < (S + 1) / 2) {
        int i = Lr--;
        int j = Rr--;
        suml -= A[i];
        suml += A[j];
        o.push_back(i);
        rest.push_back(j);
    }
    while (suml < (S + 1) / 2 && Rr >= Rl) {
        int i = Rr--;
        suml += A[i];
        rest.push_back(i);
    }
    vector<int> p;
    p.reserve(N);
    for (int i = Ll; i <= Lr; i++)
        p.push_back(i);
    for (int x : rest)
        p.push_back(x);
    for (int i = Rl; i <= Rr; i++)
        p.push_back(i);
    for (int x : o)
        p.push_back(x);
    return p;
}