#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();
    vector<pii> A(N);
    for (int i = 0; i < N; i++)
        A[i] = {A_[i], i};
    sort(A.begin(), A.end());
    ll S = 0;
    for(auto [x, i] : 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;
    pre = 0, suf = 0;
    for (int i = 1; i <= r; i++) {
        L.push_back(i - 1), R.push_back(N - i);
        pre += A[i - 1].first;
    }
    reverse(R.begin(), R.end());
    vector<int> rest;
    while (pre < (S + 1) / 2) {
        int i = L.back();
        L.pop_back();
        int j = R.back();
        R.pop_back();
        pre -= A[i].first;
        pre += A[j].first;
        rest.push_back(j);
    }
    vector<int> p;
    vector<bool> in(N);
    for (int x : L) {
        p.push_back(A[x].second);
        in[x] = true;
    }
    for (int x : rest) {
        p.push_back(A[x].second);
        in[x] = true;
    }
    for (int i = 0; i < N; i++)
        if (!in[i])
            p.push_back(A[i].second);
    return p;
}
