#include "partition.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

vector<int> solve(vector<int> A)
{
    int n = A.size();
    ll S = accumulate(A.begin(),A.end(),0LL), ans = INF;

    vector<int>perm(n);
    iota(perm.begin(),perm.end(),0);

    auto res = perm;

    do
    {
        ll curr = 0, curr_ans = INF;
        for(int i=0; i<n; i++)
        {
            int idx = perm[i];
            curr += A[idx];

            if(curr*2 >= S)
            {
                curr_ans = abs(n - 2*i - 2);
                break;
            }
        }

        if(curr_ans < ans)
        {
            ans = curr_ans;
            res = perm;
        }

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

    return res;
}
