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

using namespace std;

long long _map[10000000];

std::vector<int> solve(std::vector<int> A) {
    vector <int> bestAns;
    int bestBagsDelta = 1e9;
    int S, n = A.size();
    for(int i = 0; i < n; i++)
    {
        S += A[i];
        _map[i] = A[i];
        A[i] = i;
    }

    for(int i = 1; i <= 10100; i++)
    {
        long long s = 0;
        long long bags = 0;
        while(s < (S / 2))
        {
            s += _map[A[bags]];
            bags++;
        }
        bags = abs(n - (2 * bags));

        if(bags < bestBagsDelta)
        {
            bestBagsDelta = bags;
            bestAns = A;
        }

        next_permutation(A.begin(), A.end());
    }
    vector <int> ans;
    //for(int i : bestAns)
    //{
    //   ans.push_back(_map[i]);
    //    cout << _map[i] << ' ';
    //}
    //cout << endl;
    return bestAns;
}
