#include "partition.h"
#include <map>
#include <cmath>
#include <iostream>
using namespace std;

int n;
long long s = 0;
int best[10];
int best_first = 0;
vector<int> a;
int perm[10];

void backtrack(int i) {
    if (i >= n) {
        int sum = 0;
        int j = 0;
        while (sum < s / 2) {
            sum += a[perm[j]];

            if (sum < s / 2) {
                j++;
            }
        }
        // cerr << j << '\n';

        if (abs((j + 1) - (n - j - 1)) < abs((best_first + 1) - (n - best_first - 1))) {
            best_first = j;
            for (int k = 0; k < n; k++) {
                best[k] = perm[k];
            }
        }

        return;
    }

    for (int j = 0; j < n; j++) {
        bool ok = true;

        for (int k = 0; k < i; k++) {
            if (perm[k] == j) {
                ok = false;
                break;
            }
        }

        if (ok) {
            perm[i] = j;
            backtrack(i + 1);
        }
    }
}

std::vector<int> solve(std::vector<int> A) {
    if (A.size() == 1) return { 0 };

    a = A;
    n = A.size();
    vector<int> res(A.size());

    for (int i = 0; i < n; i++) {
        s += A[i];
    }
    
    backtrack(0);

    for (int i = 0; i < n; i++) {
        res[i] = best[i];
    }
    

    return res;
}
