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

using namespace std;

typedef int64_t ll;

std::vector<int> solve(std::vector<int> A) {
    ll S = accumulate(A.begin(), A.end(), 0LL);

    ll S2 = ceil(double(S) / 2);

    vector<int> v;

    for (ll i = 0; i < A.size(); ++i) v.push_back(i);

    vector<int> ans;
    ll diff1 = LLONG_MAX;
    ll BestSum = 0;
    do {    
        ll sum1 = 0;
        ll cnt1 = 0;
        for (ll x : v) {
            if (sum1 >= S2)  break;
            cnt1++, sum1 += A[x];
        }

        ll cnt2 = A.size() - cnt1;
        ll sum2 = S - sum1;

        ll cur_diff1 = abs(cnt1 - cnt2);
        ll cur_diff2 = abs(sum2 - sum1);

        if (cur_diff1 < diff1) {
            diff1 = cur_diff1;
            ans = v;
            BestSum = sum1;
        }

    } while (next_permutation(v.begin(), v.end()));

    //cout << diff1 << ' ' << BestSum << endl;

    return ans;
}
