#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;
    for(int x : A)
        S += x;
    // 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;
    //     }
    // }
    vector<int> L, R;
    ll suml = 0, sumr = 0;
    for (int i = 0; i < N; i++) {
        if (i < N / 2)
            L.push_back(i), suml += A[i];
        else
            R.push_back(i), sumr += A[i];
    }
    if (suml > sumr)
        swap(L, R), swap(suml, sumr);
    vector<int> rest;
    while (!L.empty() && suml < (S + 1) / 2) {
        int i = L.back();
        L.pop_back();
        int j = R.back();
        R.pop_back();
        suml -= A[i];
        suml += A[j];
        rest.push_back(j);
    }
    vector<int> p;
    vector<bool> in(N);
    for (int x : L) {
        p.push_back(x);
        in[x] = true;
    }
    for (int x : rest) {
        p.push_back(x);
        in[x] = true;
    }
    for (int i = 0; i < N; i++)
        if (!in[i])
            p.push_back(i);
    return p;
}