#include "partition.h"
#include <bits/stdc++.h>

using namespace std;

typedef int64_t ll;

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

    vector<int> idx;
    
    for (ll i = 0; i < A.size(); ++i) {
        idx.push_back(i);
    }

    ll S = accumulate(A.begin(), A.end(), 0LL);

    vector<int> ans;
    ll cnt = LLONG_MAX;

    sort(idx.begin(), idx.end());
    do {
        ll sum = 0;
        ll cur_cnt = 0;
        for (ll i = 0; i < idx.size(); ++i) {
            if (sum + A[idx[i]] < (S / 2)) {
                sum += A[idx[i]];
                //cout << idx[i] << ' ';
                cur_cnt++;
            } else {
                break;
            }
        }

        ll cur_cnt2 = (idx.size() - cur_cnt);
        if (abs(cur_cnt2 - cur_cnt) < cnt) {
            cnt = abs(cur_cnt2 - cur_cnt);
            ans = idx;
        }
    } while (next_permutation(idx.begin(), idx.end()));


    return ans;
}
