#pragma GCC optimize("Ofast")
#include "partition.h"
#include <bits/stdc++.h>
using namespace std;

std::vector<int> solve(std::vector<int> a) {
    vector<int> ans(a.size());
    vector<int> v(a.size());
    #define int long long
    int n = a.size(), sum = accumulate(a.begin(), a.end(), 0ll);
    int best = n;
    iota(v.begin(), v.end(), 0);
    int id = 1, ans_id = 0;
    do {
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur += a[v[i]];
            if (cur >= sum / 2) {
                if (abs((i + 1) - (n - i - 1)) < best) {
                    best = abs((i + 1) - (n - i - 1));
                    ans_id = id;
                }
                break;
            }
        }
        id++;
    } while (next_permutation(v.begin(), v.end()));
    int fact[n + 1];
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = fact[i - 1] * i;
    }
    bool used[n + 1];
    fill_n(used + 1, n, false);
    for (int z = 0; z < n; z++) {
        for (int i = 1; i <= n; i++) {
            if (used[i]) {
                continue;
            }
            if (ans_id <= fact[n - z - 1]) {
                ans[z] = i - 1;
                used[i] = true;
                break;
            }
            ans_id -= fact[n - z - 1];
        }
    }
    return ans;
}