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

std::vector<int> solve(std::vector<int> A)
{
    int n = A.size();

    int sum = 0;
    for(int &num : A)sum += num;
    int halfSum = (sum + 1) / 2;

    vector<int> a(n);
    for(int i=0; i<n; i++)a[i] = i;

    vector<int> v;
    for(int i=0; i<n; i++)v.push_back(i);

    int minNum = 1e9;

    do
    {
        int curSum = 0;
        int person1 = 0;

        for(int i=0; i<n; i++)
        {
            curSum += A[a[i]];
            if(curSum >= halfSum){person1 = i+1; break;}
        }

        int person2 = n-person1;

        if(minNum > abs(person1 - person2))
        {
            minNum = abs(person1 - person2);
            for(int i=0; i<n; i++)v[i] = a[i];
        }
    }
    while(next_permutation(a.begin(), a.end()));

    return v;
}
