#include "partition.h"

#define ll long long

#include <bits/stdc++.h>

using namespace std;

ll n, v[2000005] = { 0 };
ll sum = 0, sum_total = 0, nr = 0, best, pos_mx = 0;
ll crt[2000005] = { 0 }, perm[2000005] = { 0 };
vector<int> ans;

void bkt(int pos) {
    if(best <= n % 2) {
        return;
    }
    if(pos == n + 1 && best > n % 2) {
        // verific
        int nr = 0; sum = 0;
        for(int i = 1; i <= n; i++) {
            sum += v[perm[i]]; nr++;
            if(sum >= (sum_total + 1) / 2) break;
        }
        if(abs(n - nr - nr) < best) {
            best = abs(n - nr - nr);
            ans.clear();
            for(int i = 1; i <= n; i++) {
                ans.push_back(perm[i] - 1);
            }
        }
        return;
    }
    for(int i = 1; i <= n; i++) {
        if(crt[i] == 0) {
            perm[pos] = i;
            crt[i] = 1;
            bkt(pos + 1);
            crt[i] = 0;
            perm[pos] = 0;
        }
    }
}

std::vector<int> solve(std::vector<int> A) {

    sum = sum_total = nr = pos_mx = 0;

    n = A.size();
    for(int i = 1; i <= n; i++) {
        v[i] = A[i - 1];
        sum_total += v[i];
    }
    best = n;

    bkt(1);
    // cout << best << '\n';

    for(int i = 1; i <= n; i++) {
        v[i] = crt[i] = 0;
    }

    return ans;

}